P21 Merge Two Sorted Lists | Two Pointers + Dummy Node, O(m+n) Explained
Given the heads of two sorted linked lists, splice their nodes together into one sorted list and return the new head. The obvious way — dump all values into an array, sort, rebuild — works, but it throws away the one thing the problem gives you for free: both inputs are already sorted. Sorting costs extra time, and building fresh nodes costs extra space.
The classic answer is two pointers and one fake node. Create a dummy node whose .next will become the merged head, park a tail pointer on it, and walk both lists simultaneously. At every step, compare the two nodes under the pointers, splice the smaller one onto the tail, and advance only the pointer that gave up its node. Because both lists are sorted, the smaller of the two current nodes is always exactly the node the merged list needs next. When one list runs out, stop comparing and link the entire remainder of the other list in one move. Return dummy.next — no head-of-list special case ever needs writing.
Chapters
00:00 - Title
00:12 - Opening: two sorted chains, one growing result
00:46 - Naive approach: merge-into-array-sort-rebuild
01:12 - Core idea: two pointers + dummy node
01:46 - Key details: tail pointer, loop condition, the tie, tail splice
02:33 - Full walkthrough
06:28 - Complexity: O(m+n) time, O(1) space, and summary
Why the dummy node earns its keep
Every append now goes through tail.next, so the very first node is linked exactly like every later one — no "is this the head?" branch anywhere in the loop. And when the loop ends, at most one list still has nodes; a single tail.next = p1 or p2 attaches the whole remaining chain, because the leftover of a sorted list is itself sorted. Equal values (the two 1s, the tie at the start) can safely go either way.
#Algorithms #CodingInterview #Python #TwoPointers #LinkedList #DummyNode #Merge