Linked List
Dummy head to merge
Before you start
- Open lesson
Merge two sorted runs
This is the same merge, done with next links instead of indexes.
Why it matters
Ordered feeds and task queues often need to be combined while existing nodes remain shared with other code. Copying values, sorting them, and rebuilding nodes wastes both ordering and identity. Given 1 → 2 → 4 and 1 → 3 → 4, reuse all six nodes to produce one sorted list in linear time with O(1) extra space.
Example
Merge Two Sorted Lists
Merge two sorted linked lists and return the head of the merged list. Tests use value arrays.
- Input
- list1 = [1, 2, 4], list2 = [1, 3, 4]
- Output
- [1, 1, 2, 3, 4, 4]
Approach 2 · Resolve the bottleneck
The idea
Keep one example in view
Merge Two Sorted Lists
list1 = [1, 2, 4], list2 = [1, 3, 4]→[1, 1, 2, 3, 4, 4]
The baseline, Collect, sort, rebuild, is O((m + n) log(m + n)) · O(m + n). The better model below keeps this exact input and removes that bottleneck.
With heads 1 and 1, attach list1's 1; next compare 2 with list2's 1 and attach that 1. A dummy head makes each splice uniform, while head-by-head merging avoids brute copying, sorting, and allocating six replacement nodes.
Create a dummy node and put tail on it. The two heads are both 1, so attach list1's 1 and advance list1. Now compare 2 with list2's 1; attach list2's 1. tail advances after every attachment.
Continue with 2, then 3, then list1's 4. list1 is empty, so one link attaches list2's remaining 4. dummy.next points to the first real 1. The temporary dummy is new, but every result node is one of the six input nodes.
Pro
The rest of this is on Pro
The idea above is free. The walkthrough, the cost, and the practice are on Pro.