Merge Two Sorted Lists

Merge Two Sorted Lists

Merge Two Sorted Lists

Problem

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

Merge them into one sorted list. The new list must be made by splicing together the nodes of the two lists. We do not create new nodes with values. We reuse the existing nodes.

Return the head of the merged list.

Examples

Example 1

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2

Input: list1 = [], list2 = []
Output: []

Example 3

Input: list1 = [], list2 = [0]
Output: [0]

Constraints

• The number of nodes in each list is between 0 and 50.
• -100 <= Node.val <= 100
• Both lists are sorted in non-decreasing order.

Main Idea

Both lists are already sorted. So the smallest value is always at the front of one of the two lists.

We build the merged list step by step:

• Compare the head of list1 with the head of list2.
• Attach the smaller node to the end of the merged list.
• Move forward in the list that gave the node.
• Repeat until one list is empty.
• Attach the rest of the other list. It is already sorted, so we can attach it all at once.

The dummy node trick

We need a starting point for the merged list. But we do not know yet which node will be the first one. A dummy node solves this problem.

• We create a fake node called curr. It is only a placeholder.
• We use a pointer called dummy that always points to the last node of the merged list.
• At the end, the real head is curr.next. We skip the fake node.

Note: The names in the code can be confusing. curr is the fake starting node, and dummy is the moving tail pointer. In the explanation below, we call curr the "dummy head" and dummy the "tail".

ListNode Class

LeetCode already gives this class. It is shown here so the code is complete.

function ListNode(val, next) {
    this.val = (val === undefined ? 0 : val);
    this.next = (next === undefined ? null : next);
}

Solution: Iterative with Dummy Node

var mergeTwoLists = function (list1, list2) {
    // fake starting node
    let curr = new ListNode();

    // tail: always points to the last node of the merged list
    let dummy = curr;

    while (list1 !== null && list2 !== null) {
        if (list1.val >= list2.val) {
            // list2 has the smaller (or equal) value, so attach it
            dummy.next = list2;
            list2 = list2.next;
        } else {
            // list1 has the smaller value, so attach it
            dummy.next = list1;
            list1 = list1.next;
        }

        // move the tail to the node we just added
        dummy = dummy.next;
    }

    // attach the remaining nodes of the list that is not finished
    if (list1) {
        dummy.next = list1;
    } else {
        dummy.next = list2;
    }

    // skip the fake node
    return curr.next;
};

How the Code Works

Step 1: Create the dummy head and the tail

• curr = new ListNode() is the fake node. Its value is not used.
• dummy = curr is the tail. At the start, the tail is the fake node.

Step 2: Loop while both lists have nodes

• We compare list1.val and list2.val.
• If list1.val >= list2.val, we attach list2's node, and move list2 one step forward.
• Otherwise, we attach list1's node, and move list1 one step forward.
• After attaching, we move the tail: dummy = dummy.next.

When both values are equal, we take from list2. This is fine, because equal values can be in any order.

Step 3: Attach the leftover nodes

• The loop stops when one list becomes null.
• The other list may still have nodes. They are all bigger than or equal to what we added, and they are already sorted.
• So we attach the whole rest with one line: dummy.next = list1 or dummy.next = list2.
• If both lists are empty, list2 is null, so dummy.next = null. The result is an empty list.

Step 4: Return the real head

• curr.next is the first real node. We return it.
• For two empty lists, curr.next is null, which is the correct answer.

Dry Run

Let us take list1 = [1, 2, 4] and list2 = [1, 3, 4].

• list1 still has the node 4. We attach it.
• The final list is [1, 1, 2, 3, 4, 4].

Now let us take list1 = [] and list2 = [0].

• The loop does not run, because list1 is null.
• list1 is empty, so we do dummy.next = list2.
• The result is [0].

Recursive Solution (Optional)

We can also solve it with recursion.

• If one list is empty, return the other list.
• The smaller head becomes the head of the result.
• Its next is the merge of the rest.

var mergeTwoLists = function (list1, list2) {
    // if one list is empty, return the other one
    if (list1 === null) return list2;
    if (list2 === null) return list1;

    if (list1.val <= list2.val) {
        // list1 has the smaller head
        list1.next = mergeTwoLists(list1.next, list2);
        return list1;
    } else {
        // list2 has the smaller head
        list2.next = mergeTwoLists(list1, list2.next);
        return list2;
    }
};

Complexity

• Time Complexity: O(m + n)
  • Each call handles one node.
• Space Complexity: O(m + n)
  • The recursion stack goes as deep as the total number of nodes.

Complexity

• Time Complexity: O(m + n)
  • m and n are the sizes of the two lists.
  • Each node is visited once, and each step takes O(1) time.
• Space Complexity: O(1)
  • We reuse the existing nodes and only create one fake node.
  • We use only a few pointers.

Comparison

Summary

• Both lists are sorted, so the smallest value is always at one of the two heads.
• A dummy node gives us a safe starting point, so we do not need special code for the first node.
• At each step, we attach the smaller node and move that list forward.
• When one list ends, we attach the rest of the other list in one step.
• We return curr.next, which skips the dummy node.
• The iterative solution runs in O(m + n) time and uses O(1) space.