Merge Two Sorted Lists LeetCode 21

LeetCode 21 — Merge Two Sorted Lists — gives you the heads of two sorted linked lists list1 and list2. You must merge them into one sorted linked list by splicing the existing nodes together — no new nodes, just relinking. Return the head of the merged list.

For example, list1 = [1,2,4] and list2 = [1,3,4] yields [1,1,2,3,4,4]. The key constraint is that you must use the existing nodes rather than creating new ones; this is a pointer manipulation problem, not a copy problem. Both lists are already sorted in non-decreasing order, so you only need to compare heads at each step.

The problem is rated Easy but it is foundational: mastering it is a prerequisite for Sort List (LeetCode 148), Merge K Sorted Lists (LeetCode 23), and understanding the merge phase of merge sort. The two standard approaches — iterative with a dummy node and recursive — each illuminate a different way of thinking about linked list construction.

The iterative approach creates a single dummy node before the loop begins. A current pointer starts at the dummy. On each iteration, compare the values at the heads of list1 and list2. Attach the smaller node to current.next, then advance that list's pointer forward by one node. Advance current to current.next as well.

When the while loop ends — because one list is exhausted — attach the remaining list directly to current.next. Since the remaining list is already sorted, there is nothing more to compare; the entire tail can be appended in one assignment. Return dummy.next as the head of the merged result.

The dummy node is the key insight. Without it you would need special logic to figure out which of list1 or list2 provides the first node of the merged result, and you would need to set the head pointer separately. The dummy node absorbs that edge case: current always has a valid .next slot to write into, and dummy.next is always the answer regardless of which list won the first comparison.

Trace the algorithm on list1 = [1,2,4] and list2 = [1,3,4]. Dummy → current. Step 1: compare 1 vs 1. Tie goes to list1 (or list2, either works): attach list1's 1, advance list1 to 2, advance current. Step 2: compare 2 vs 1. list2 wins: attach list2's 1, advance list2 to 3, advance current. Step 3: compare 2 vs 3. list1 wins: attach 2, advance list1 to 4. Step 4: compare 4 vs 3. list2 wins: attach 3, advance list2 to 4. Step 5: compare 4 vs 4. Attach list1's 4, advance list1 to null.

Now list1 is exhausted. Attach remaining list2 (just the node 4) to current.next. The loop terminates. Return dummy.next which is the 1 node from list1, the head of [1,1,2,3,4,4]. Total comparisons: 5, total iterations: 5, both lists fully consumed.

The time complexity is O(m+n) because every node is visited exactly once. The space complexity is O(1) because only the dummy node and current pointer are allocated — no extra array or recursive stack. The dummy node itself is a local variable that is not returned, so it does not count against output space.

The recursive approach is beautifully concise. Base case: if either list is null, return the other. Recursive case: compare the heads. The list with the smaller head "wins" — set winner.next = merge(winner.next, other), then return winner. The recursion naturally builds the merged list by deciding which node comes first at each level of the call stack.

For list1 = [1,2,4] and list2 = [1,3,4]: merge(1→2→4, 1→3→4). list1.val (1) <= list2.val (1), so list1 wins. list1.next = merge(2→4, 1→3→4). Now 2 vs 1: list2 wins. list2.next = merge(2→4, 3→4). 2 vs 3: list1 wins. list1.next = merge(4, 3→4). 4 vs 3: list2 wins. list2.next = merge(4, 4). Tie: list1 wins. list1.next = merge(null, 4) = 4. Unwind: produces [1,1,2,3,4,4].

The recursive approach uses O(m+n) call stack space — one frame per node processed. For very long lists this risks a stack overflow, which the iterative approach avoids entirely. However, for interview purposes and for the problem constraints (up to 50 nodes each), the recursive solution is perfectly valid and often preferred for its readability.

Merge Two Sorted Lists is literally the merge step of merge sort. Merge sort splits the array (or list) in half recursively until each piece is a single element, then merges sorted pieces back together. The merge operation is exactly what LeetCode 21 implements: given two sorted sequences, produce one sorted sequence by repeatedly selecting the smaller front element.

Understanding LeetCode 21 deeply is the prerequisite for Sort List (LeetCode 148), which asks you to sort a linked list in O(n log n) time. The optimal solution is bottom-up merge sort on the linked list, with LeetCode 21's iterative merge as the inner subroutine. Each pass merges pairs of sorted sublists of increasing length (1, 2, 4, 8, ...) until the whole list is sorted.

Merge K Sorted Lists (LeetCode 23) extends the pattern further: instead of merging two lists you merge k lists simultaneously using a min-heap. The heap always gives you the current minimum across all k list heads. Once you understand that LeetCode 23 is just LeetCode 21 repeated with a priority queue managing the "which list head is smallest" comparison, the harder problem becomes approachable.

Python iterative: def mergeTwoLists(l1, l2): dummy = ListNode(0); cur = dummy; while l1 and l2: if l1.val <= l2.val: cur.next = l1; l1 = l1.next; else: cur.next = l2; l2 = l2.next; cur = cur.next; cur.next = l1 if l1 else l2; return dummy.next. Python recursive: def mergeTwoLists(l1, l2): if not l1: return l2; if not l2: return l1; if l1.val <= l2.val: l1.next = mergeTwoLists(l1.next, l2); return l1; else: l2.next = mergeTwoLists(l1, l2.next); return l2.

Java iterative: public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(0); ListNode cur = dummy; while (l1 != null && l2 != null) { if (l1.val <= l2.val) { cur.next = l1; l1 = l1.next; } else { cur.next = l2; l2 = l2.next; } cur = cur.next; } cur.next = (l1 != null) ? l1 : l2; return dummy.next; }. Java recursive: if l1 == null return l2; if l2 == null return l1; if l1.val <= l2.val { l1.next = merge(l1.next, l2); return l1; } else { l2.next = merge(l1, l2.next); return l2; }.

Time complexity for both approaches: O(m+n) where m and n are the lengths of the two lists — every node is processed exactly once. Space complexity: iterative O(1) auxiliary space (just the dummy node and current pointer, no stack); recursive O(m+n) call stack space due to one frame per node merged. For the problem constraints both are acceptable; for production code on very long lists, prefer iterative.

Merge K Sorted Lists (LeetCode 23) is the direct generalization: merge k sorted linked lists using a min-heap of size k. The heap always holds the current head of each non-exhausted list. Pop the minimum, append it to the result, and push that list's next node. This runs in O(n log k) where n is total nodes. The inner merge logic is identical to LeetCode 21.

Sort List (LeetCode 148) uses bottom-up merge sort with LeetCode 21's iterative merge as the core subroutine. It achieves O(n log n) time and O(1) space — the iterative bottom-up approach avoids the O(log n) recursive stack that top-down merge sort would use. The step sizes 1, 2, 4, 8, ... determine which pairs of sublists to merge in each pass.

Add Two Numbers (LeetCode 2) follows the same two-pointer traversal pattern: advance through two linked lists simultaneously, combine values (with carry), and build a result list. Reorder List (LeetCode 143) combines finding the middle node, reversing the second half, and then interleaving — the interleave step is essentially a merge of two lists. These problems share the structural DNA of LeetCode 21: traverse two lists in lockstep, stitch together results.