Problem Statement #

Merge two sorted linked lists and return it as a new sorted list. The new list should be made by splicing together the nodes of the first two lists.

Example:

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

Definition for singly-linked list:

function ListNode(val) {
    this.val = val;
    this.next = null;
}

Solution #

var mergeTwoLists = function(l1, l2) {
    let cur1 = l1;
    let cur2 = l2;
    let result = new ListNode();
    const head = result;

    while (cur1 && cur2) {
        if (cur2.val >= cur1.val) {
            result.next = new ListNode(cur1.val);
            cur1 = cur1.next;
            console.log("hit 1");
        }
        else {
            result.next = new ListNode(cur2.val);
            cur2 = cur2.next;
            console.log("hit 2");
        }
        result = result.next;
    }
    
    // Add on remaining nodes
    if (cur1) {
        result.next = cur1;
    }
    if (cur2) {
        result.next = cur2;
    }
    
    return head.next;
};

Approach and Algorithm Explanation #

The algorithm employs a two-pointer technique with a dummy head node to elegantly merge two sorted linked lists. Let’s break down the solution step by step:

Initial Setup #

We begin by creating three pointers: cur1 and cur2 point to the heads of the input lists, while result is a dummy node that serves as the starting point for our merged list. We also maintain a reference to this dummy head so we can return the actual merged list later (starting from head.next).

Main Merging Loop #

The core logic resides in the while (cur1 && cur2) loop, which continues as long as both linked lists have remaining nodes. This condition is crucial because our comparison operations require values from both lists.

At each iteration, we compare the values at cur1 and cur2. We select the node with the smaller value and attach it to our result list. After attaching a node, we advance the pointer of the list we just used (either cur1 or cur2) to avoid processing the same node twice. We also advance the result pointer to prepare for the next node attachment.

This approach ensures that at every step, we’re adding the smallest available value to our merged list, maintaining the sorted order throughout the process.

Handling Remaining Nodes #

After the main loop terminates, one of two scenarios exists: either both lists are exhausted (both are null), or one list still has remaining nodes. The beauty of linked lists shines here—we don’t need to iterate through the remaining nodes one by one.

Since the remaining portion of either list is already sorted and properly linked, we can simply attach it to the end of our result list. This is analogous to connecting train cars: when you attach a second train to the first, you only need to connect the locomotives; all the subsequent cars remain connected automatically.

If cur1 still has nodes, we set result.next = cur1. Similarly, if cur2 has remaining nodes, we set result.next = cur2. Note that only one of these conditions can be true (or neither if both lists were the same length), so there’s no conflict.

Time and Space Complexity #

Time Complexity: O(n + m), where n and m are the lengths of the two input lists. We visit each node exactly once during the merge process.

Space Complexity: O(1) if we don’t count the output list. We only use a constant amount of extra space for pointers. The new nodes created are part of the required output, not auxiliary space.

Alternative Approach: In-Place Merging #

The current solution creates new ListNode objects during the merge. For a more space-efficient approach, we could reuse the existing nodes from the input lists:

var mergeTwoListsInPlace = function(l1, l2) {
    let dummy = new ListNode();
    let current = dummy;
    
    while (l1 && l2) {
        if (l1.val <= l2.val) {
            current.next = l1;
            l1 = l1.next;
        } else {
            current.next = l2;
            l2 = l2.next;
        }
        current = current.next;
    }
    
    current.next = l1 || l2;
    
    return dummy.next;
};

This version doesn’t create new nodes; instead, it rewires the existing nodes’ pointers, making it more memory efficient.

Key Insights #

1. Dummy Head Pattern: Using a dummy head node simplifies edge cases and eliminates the need for special handling of the first node.

2. Two-Pointer Technique: Maintaining separate pointers for each list allows us to traverse both lists simultaneously while making comparisons.

3. Efficient Tail Handling: Recognizing that remaining nodes don’t need individual processing saves both time and code complexity.

4. Comparison Logic: The condition cur2.val >= cur1.val ensures stability—when values are equal, we take from the first list, though either choice maintains correctness for this problem.

This problem serves as an excellent foundation for understanding linked list manipulation and is frequently used as a building block in more complex algorithms, such as merge sort for linked lists.