Insert Interval into Sorted List in DSA C - Execution Trace

Concept Flow - Insert Interval into Sorted List

Create new interval node

↓

Start at head of sorted list

↓

Traverse list while current.end < new.start

↓

Check overlap with current interval

Yes No↓

Merge intervals

↓

Adjust pointers

↓

Continue merging if needed

↓

Finish insertion

Create a new interval node, traverse the sorted list to find the correct position, merge overlapping intervals, and insert the new or merged interval maintaining sorted order.

Execution Sample

DSA C

struct Interval {
  int start;
  int end;
  struct Interval* next;
};

// Insert new interval into sorted list with merging

This code inserts a new interval into a sorted linked list of intervals, merging overlaps.

Execution Table

Step	Operation	Current Node	Pointer Changes	Visual State
1	Create new interval [4, 9]	N/A	new = [4,9]->NULL	[1,3]->[6,7]->[8,10]->[12,16]->NULL
2	Start at head	[1,3]	current = head	[1,3]->[6,7]->[8,10]->[12,16]->NULL
3	Check if current.end < new.start (3 < 4)	current=[1,3]	Move prev=current, current=current.next	prev=[1,3], current=[6,7]
4	Check if current.end < new.start (7 < 4)	current=[6,7]	Condition false, stop traversal	prev=[1,3], current=[6,7]
5	Check overlap: new.start <= current.end (4 <= 7)	current=[6,7]	Merge: new.start = min(4,6)=4, new.end = max(9,7)=9	new=[4,9]
6	Remove current [6,7] from list	current=[6,7]	prev.next = current.next ([8,10])	List: [1,3]->[8,10]->[12,16]
7	Check next node [8,10] overlap with new [4,9]	current=[8,10]	Overlap: merge new.end = max(9,10)=10	new=[4,10]
8	Remove current [8,10]	current=[8,10]	prev.next = current.next ([12,16])	List: [1,3]->[12,16]
9	Check next node [12,16] overlap with new [4,10]	current=[12,16]	No overlap (12 > 10), stop merging	List: [1,3]->[12,16]
10	Insert merged new interval after prev	prev=[1,3]	new.next = prev.next; prev.next = new	List: [1,3]->[4,10]->[12,16]
11	Insertion complete	N/A	N/A	[1,3]->[4,10]->[12,16]->NULL

💡 Traversal stops when no more overlapping intervals are found and new interval is inserted.

Variable Tracker

Variable	Start	After Step 3	After Step 4	After Step 6	After Step 8	After Step 10	Final
current	[1,3]	[6,7]	[6,7]	[8,10]	[12,16]	[12,16]	NULL
prev	NULL	[1,3]	[1,3]	[1,3]	[1,3]	[1,3]	[1,3]
new	Created [4,9]	[4,9]	[4,9]	[4,9]	[4,10]	[4,10]	[4,10]
List	[1,3]->[6,7]->[8,10]->[12,16]	[1,3]->[6,7]->[8,10]->[12,16]	[1,3]->[6,7]->[8,10]->[12,16]	[1,3]->[8,10]->[12,16]	[1,3]->[12,16]	[1,3]->[4,10]->[12,16]	[1,3]->[4,10]->[12,16]

Key Moments - 3 Insights

Why do we move 'prev' and 'current' pointers during traversal?

We move 'prev' and 'current' to find the correct position where the new interval fits without overlap. See execution_table steps 3 and 4 where 'prev' points to [1,3] and 'current' moves forward.

How do we merge overlapping intervals?

When intervals overlap, we update the new interval's start to the minimum start and end to the maximum end, removing the overlapping node from the list. See steps 5, 7, and 8 in the execution_table.

Why do we insert the new interval after 'prev'?

Because 'prev' points to the last interval before the new merged interval, inserting after 'prev' keeps the list sorted. See step 10 where new is linked after 'prev'.

Visual Quiz - 3 Questions

Look at the execution_table, what is the 'new' interval after step 7?

A [4,9]

B [4,10]

C [6,7]

D [8,10]

💡 Hint

Check the 'new' variable value in execution_table row 7 where merging with [8,10] happens.

At which step does the traversal stop because there is no overlap with the next node?

A Step 4

B Step 6

C Step 9

D Step 10

💡 Hint

Look at execution_table step 9 where the next node [12,16] does not overlap with new [4,10].

If the new interval was [5,6] instead of [4,9], how would the list look after insertion?

A [1,3]->[5,7]->[8,10]->[12,16]

B [1,3]->[4,10]->[12,16]

C [1,3]->[5,6]->[6,7]->[8,10]->[12,16]

D ]61,21[>-]01,8[>-]7,5[>-]3,1[

💡 Hint

Consider merging [5,6] with overlapping intervals [6,7] and [8,10] as in the variable_tracker.

Concept Snapshot

Insert Interval into Sorted List:
- Traverse list until current.end < new.start
- Merge overlapping intervals by updating new.start and new.end
- Remove merged intervals from list
- Insert merged new interval after prev
- Maintains sorted order and merges overlaps
- Handles empty list or no overlap cases

Full Transcript

This concept shows how to insert a new interval into a sorted linked list of intervals. We create a new interval node, then traverse the list to find where it fits. While traversing, we move pointers 'prev' and 'current' to find the correct position. If intervals overlap, we merge by updating the new interval's start and end to cover all overlaps, removing the old overlapping nodes. Finally, we insert the merged interval after 'prev' to keep the list sorted. The execution table tracks each step, pointer changes, and the list's visual state. Key moments clarify why pointers move, how merging works, and why insertion happens after 'prev'. The visual quiz tests understanding of these steps and changes. This method ensures the list remains sorted and merged after insertion.