Merge Linked Lists

Concept

Problem: You are given the heads of two sorted linked lists, list1 and list2. Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

This problem tests your ability to manipulate pointers across multiple lists simultaneously. It is exactly the same logic used in the “Merge” step of the Merge Sort algorithm.

Mental Model

L1: 1 -> 2 -> 4
L2: 1 -> 3 -> 4

We use the Dummy Node pattern. We create a fake dummy node, and a current pointer sitting on it.
We look at L1.val and L2.val.
1 is equal to 1. Let’s pick L1.

• current.next points to L1.
• Move L1 forward.
• Move current forward.

Now, L1 is at 2, and L2 is at 1.
1 is smaller than 2. Pick L2.

• current.next points to L2.
• Move L2 forward.
• Move current forward.

Implementation

// Time Complexity: O(N + M)
// Space Complexity: O(1) (We don't create new nodes, just rewire pointers)
function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
    // The Dummy Node saves us from nasty edge cases (like empty lists)
    const dummy = new ListNode(-1);
    let current = dummy;

    // While both lists still have nodes to compare...
    while (list1 !== null && list2 !== null) {
        if (list1.val <= list2.val) {
            current.next = list1;
            list1 = list1.next;
        } else {
            current.next = list2;
            list2 = list2.next;
        }
        current = current.next;
    }

    // One list finished early. The other list might still have 50 nodes left!
    // Because they are already sorted and physically linked together, 
    // we can just attach the entire remaining tail in one O(1) operation.
    if (list1 !== null) {
        current.next = list1;
    } else {
        current.next = list2;
    }

    return dummy.next;
}

Recursive Approach

Like almost all Linked List problems, this can be solved recursively.
The recursive approach is highly elegant, but uses $O(N+M)$ Call Stack space.

function mergeTwoListsRecursive(list1: ListNode | null, list2: ListNode | null): ListNode | null {
    if (list1 === null) return list2;
    if (list2 === null) return list1;

    if (list1.val <= list2.val) {
        // List 1 is smaller. It wins the current spot.
        // What comes next? The result of merging everything else!
        list1.next = mergeTwoListsRecursive(list1.next, list2);
        return list1;
    } else {
        list2.next = mergeTwoListsRecursive(list1, list2.next);
        return list2;
    }
}

Interview Questions

Q: A harder variation of this problem is “Merge K Sorted Lists” (e.g., merging 100 linked lists together). Could you just use this mergeTwoLists function over and over again?
A: Yes, you could. You could merge List 1 and 2, then merge the result with List 3, etc. However, this is incredibly slow ($O(K \times N)$ time), because the merged list gets longer every time, and you are repeatedly traversing the same nodes over and over.
To optimally merge $K$ sorted lists, you should use a Min-Heap (Priority Queue). You dump the Head of all 100 lists into the Min-Heap. The Heap instantly hands you the absolute smallest node. You attach it to your result, and then push that node’s next back into the Heap. This achieves the mathematically optimal $O(N \log K)$ time complexity.

Q: Why do we create const dummy = new ListNode(-1)? Doesn’t that consume extra memory?
A: Yes, it consumes exactly $O(1)$ memory (a single node). This microscopic memory penalty is vastly outweighed by the cleaner code. Without the Dummy Node, we would have to write complex if/else checks inside our while loop to figure out if this is the very first node being inserted so we can manually initialize the actual head variable. The Dummy Node allows us to treat the very first insertion exactly the same as the 100th insertion.