Merge Two Sorted Lists Solution

Problem

Two sorted linked lists need to be merged into one sorted linked list. The result must be assembled by rewiring the existing nodes — no new nodes are created. Given list1 = [1→2→4] and list2 = [1→3→4], the merged output is:

→

→∅

[1,1,2,3,4,4]

Input: list1 = [1→2→4], list2 = [1→3→4]
Output: [1→1→2→3→4→4]
Explanation: At each step, whichever head is smaller gets appended to the result, and that list advances by one node.

Intuition

Since both lists are already sorted, the globally smallest remaining element is always at one of the two heads. We can build the merged list greedily — compare the two heads, take the smaller one, and repeat. Once one list is exhausted, the other can be attached wholesale in a single pointer assignment rather than node by node.

Approach 1 — Recursive

The recursive structure mirrors the problem: the merged list starting from two heads is the smaller head with its next pointer rewired to the recursive merge of the remaining elements.

If either list is null, return the other (base case — nothing left to merge).
Compare the two heads to find the smaller one.
Set the smaller head's .next to the recursive merge of that node's next and the other head.
Return the smaller head as the new front of the merged list.

1class Solution:
2    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
3        if not list1:
4            return list2
5        if not list2:
6            return list1
7
8        if list1.val <= list2.val:
9            list1.next = self.mergeTwoLists(list1.next, list2)  # rewire before returning
10            return list1
11        else:
12            list2.next = self.mergeTwoLists(list1, list2.next)
13            return list2

Time: O(m + n) — each node is visited exactly once across all recursive calls.
Space: O(m + n) — the call stack grows one frame per node visited before hitting a base case.

Approach 2 — Iterative with Dummy Head

Eliminate call-stack overhead by building the result in a loop. A dummy sentinel node at the front makes the loop uniform — no special case needed to initialize the result head.

Create a dummy node and point current to it.
While both lists are non-empty, compare their heads and wire the smaller node to current.next; advance that list and current.
When one list runs out, attach the entire remaining list in one assignment — no loop needed, it's already sorted.
Return dummy.next to skip the placeholder node.

1class Solution:
2    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
3        dummy = ListNode(0)
4        current = dummy
5
6        while list1 and list2:
7            if list1.val <= list2.val:
8                current.next = list1
9                list1 = list1.next
10            else:
11                current.next = list2
12                list2 = list2.next
13            current = current.next
14
15        current.next = list1 if list1 else list2  # attach remaining tail in O(1)
16
17        return dummy.next

Time: O(m + n) — each node is visited exactly once.
Space: O(1) — only a constant number of extra pointers regardless of list length.

Complexity Summary

Approach	Time	Space	When to use
Recursive	O(m + n)	O(m + n)	Short lists or when the recursive structure clarifies the logic
Iterative (Dummy Head)	O(m + n)	O(1)	Production code or very long lists where stack overflow is a concern

Common Mistakes

Looping to append the tail instead of a single assignment — once one list is exhausted, current.next = remaining_list is O(1) and attaches all remaining nodes at once; iterating through them wastes time and is unnecessary.
Not using a dummy head — without the sentinel, the first iteration requires a special case to initialize the result head; the dummy node makes every iteration identical and eliminates that branch.
In the recursive solution, forgetting to return the selected node — the function must both reassign node.next and return that node; doing only one produces a truncated or disconnected result.
Advancing the wrong pointer after attach — after wiring current.next = list1, you must advance list1 = list1.next before current = current.next, or list1 no longer points to the next unprocessed node.
Returning dummy instead of dummy.next — dummy is a placeholder with value 0 that was never part of either input; the real merged list starts at dummy.next.

Merge Two Sorted Lists — Solution