Merge Two Sorted Lists

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one sorted linked list and return the head of the new sorted list. The new list should be made up of nodes from list1 and list2.

Examples

• 0 ≤ length of each list ≤ 100
• -100 ≤ Node.val ≤ 100
• Both list1 and list2 are sorted in non-decreasing order.

Prerequisites

Before attempting this problem, you should be comfortable with:

• Linked Lists — node structure with val and next pointer
• Dummy Nodes — using a sentinel node to avoid special-casing the head of the result list
• Two Pointers — advancing two pointers simultaneously through separate data structures
• Recursion — solving subproblems by breaking off the head and recursing on the rest

1. Recursion

Intuition

Merging two sorted lists recursively is elegant: at each step, pick whichever head is smaller and attach it to the result of merging the rest. Since both lists are already sorted, the smaller head must be the next node in the merged list.

The base cases handle empty lists: if either list is None, return the other — there is nothing left to merge.

Algorithm

• If list1 is None, return list2.
• If list2 is None, return list1.
• If list1.val ≤ list2.val: set list1.next = mergeTwoLists(list1.next, list2), return list1.
• Otherwise: set list2.next = mergeTwoLists(list1, list2.next), return list2.

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if list1 is None:
            return list2
        if list2 is None:
            return list1
        if list1.val <= list2.val:
            list1.next = self.mergeTwoLists(list1.next, list2)
            return list1
        else:
            list2.next = self.mergeTwoLists(list1, list2.next)
            return list2

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) return list2;
        if (list2 == null) return list1;
        if (list1.val <= list2.val) {
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }
}

Time Complexity: O(n + m) — each node visited once.
Space Complexity: O(n + m) — recursion stack depth equals total nodes.

2. Iteration (Two Pointer + Dummy Node)

Intuition

Build the merged list step-by-step with two pointers, one into each list. At each step compare the current heads and attach the smaller one to the end of the merged list. A dummy sentinel node at the start eliminates all special-casing for the head — dummy.next is always the answer.

When the main loop ends (one list is exhausted), simply link the non-empty list's remaining tail. Since both lists were sorted, the remaining nodes are already in order.

Algorithm

• Create a dummy = ListNode(0) sentinel. Set node = dummy.
• While both list1 and list2 are non-null:
• If list1.val < list2.val: node.next = list1; advance list1 = list1.next.
• Else: node.next = list2; advance list2 = list2.next.
• Always advance node = node.next.
• After the loop: node.next = list1 or list2 (whichever is non-null).
• Return dummy.next.

Common Pitfalls

Forgetting to Handle Empty Lists

Not checking if one or both lists are null before starting the merge leads to null pointer exceptions. If list1 is empty, the answer is simply list2, and vice versa. In the iterative version the while-loop handles this naturally — but in the recursive version you must explicitly return early.

Not Attaching the Remaining Nodes

After the comparison loop, one list may still have remaining nodes. A common mistake is skipping node.next = list1 or list2. Since both lists are sorted and one is exhausted, all remaining nodes in the other list are already in the correct order — just link the tail.

# Wrong — loop ends, tail is not linked:
while list1 and list2:
    ...
return dummy.next  # remaining nodes are lost!

# Correct — attach the leftover tail:
node.next = list1 or list2
return dummy.next

Using <= vs < in the Comparison

Using list1.val <= list2.val (with equals) means equal values from list1 always go first — both are correct since the merged list just needs to be non-decreasing. Be consistent: the recursive and iterative versions differ by a sign (< vs <=) but produce the same correctness guarantee. Pick one and stick with it.

Skipping the Dummy Node

Without a dummy node you need a special case to set the head of the merged list. With a dummy, node.next = ... works uniformly from the very first iteration. Always return dummy.next, not dummy.