Merge Two Sorted Lists —
Compare heads. Stitch the smaller one.
Merging two sorted linked lists into one is a fundamental operation — it's the linked-list equivalent of merging sorted arrays, and the core of merge sort on lists. Two pointers compare heads and stitch the smaller node into the result. Watch each comparison and pointer redirect on LearnBug and the merge becomes mechanical.
What is the problem?
Given the heads of two sorted linked lists, return the head of one merged sorted list. You must reuse the existing nodes — no new node creation. At each step, compare the current heads of both lists and attach the smaller one to the result. When one list is exhausted, attach the remainder of the other.
The dummy head trick
Creating a dummy (sentinel) head node eliminates the special case of initialising the result list's head. You build the merged list starting from dummy.next and return that. On LearnBug you see the dummy node at the start and the result chain growing from it as each comparison picks the next node.
L1: 1→3→5 and L2: 2→4→6
Create dummy node. curr = dummy.
Dummy is our anchor. We'll return dummy.next at the end.
L1
L2
1 < 2 → attach 1, advance p1
L1 head (1) is smaller. Attach node 1 to result. p1 advances to 3.
3 > 2 → attach 2, advance p2
L2 head (2) is smaller. Attach 2. p2 advances to 4.
3 < 4 → attach 3. Then 5 > 4 → attach 4. Then 5 < 6 → attach 5.
Alternating picks. Each comparison attaches one node and advances that list's pointer.
p1 exhausted — attach remaining L2 (just 6)
p1 is None. Attach curr.next = p2 directly — no more comparisons needed.
Return dummy.next = 1→2→3→4→5→6 ✓
Iterative with dummy head
def merge_two_lists(l1, l2):
dummy = ListNode(0) # sentinel node
curr = dummy
while l1 and l2:
if l1.val <= l2.val:
curr.next = l1
l1 = l1.next
else:
curr.next = l2
l2 = l2.next
curr = curr.next
curr.next = l1 or l2 # attach remaining list
return dummy.next # skip the dummydef merge_two_lists_recursive(l1, l2):
if not l1: return l2 # base cases
if not l2: return l1
if l1.val <= l2.val:
l1.next = merge_two_lists_recursive(l1.next, l2)
return l1
else:
l2.next = merge_two_lists_recursive(l1, l2.next)
return l2Time & Space Complexity
Frequently asked questions
Why use a dummy head node?
Without a dummy, you'd need to check which list has the smaller first element to set the result head, then handle the rest of the loop differently. A dummy node lets the loop run uniformly from the very first comparison — you always set curr.next and advance curr. Return dummy.next to skip the dummy at the end.
What does curr.next = l1 or l2 do?
In Python, l1 or l2 returns l1 if it's truthy (not None), otherwise returns l2. After the loop, exactly one list is exhausted. This one-liner attaches whichever list still has nodes remaining — cleaner than two separate if statements.
How does this extend to merging K sorted lists?
For K sorted lists, use a min-heap of (value, list_index, node) tuples. Always pop the minimum, attach it to result, and push that node's next. Total time O(N log K) where N is total nodes. This is LeetCode 23 — Merge K Sorted Lists, one of the most commonly asked hard problems.
What is the LeetCode problem for this?
LeetCode 21 — Merge Two Sorted Lists. One of the most common easy linked list problems. The dummy head and iterative approach are the expected solutions. Direct follow-ups: LC 23 (Merge K Sorted Lists), LC 148 (Sort List — uses merge sort with this merge step), and LC 88 (Merge Sorted Array — same idea on arrays).
Does this create new nodes or reuse existing ones?
It reuses existing nodes — no new node allocation (except the dummy head which is discarded). The pointers of existing nodes are redirected. This is O(1) extra space. In contrast, building a new list by creating new nodes at each step would be O(n + m) space — correct but wasteful.
Watch nodes stitch together from two lists into one
Paste your two sorted lists into LearnBug and see every comparison and pointer redirect step by step.