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 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;
    }

    // Attach remaining nodes
    current.next = l1 || l2;

    return dummy.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 a dummy node that serves as the starting point for our merged list. We also maintain a current pointer that tracks where to attach the next node. The dummy node pattern simplifies edge cases and eliminates the need for special handling of the first node.

Main Merging Loop #

The core logic resides in the while (l1 && l2) 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 l1 and l2. 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 l1 or l2) to move to the next node. We also advance the current 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.

The line current.next = l1 || l2 elegantly handles all cases:

• If l1 has remaining nodes, attach l1
• If l2 has remaining nodes, attach l2
• If both are null, current.next becomes null (proper list termination)

Visual Example #

Let’s trace through merging 1->2->4 and 1->3->4:

Initial: l1 = 1->2->4, l2 = 1->3->4, current = dummy

Step 1: l1.val (1) <= l2.val (1)
  Attach l1(1), advance l1
  Result: dummy->1, l1 = 2->4, l2 = 1->3->4

Step 2: l1.val (2) > l2.val (1)
  Attach l2(1), advance l2
  Result: dummy->1->1, l1 = 2->4, l2 = 3->4

Step 3: l1.val (2) <= l2.val (3)
  Attach l1(2), advance l1
  Result: dummy->1->1->2, l1 = 4, l2 = 3->4

Step 4: l1.val (4) > l2.val (3)
  Attach l2(3), advance l2
  Result: dummy->1->1->2->3, l1 = 4, l2 = 4

Step 5: l1.val (4) <= l2.val (4)
  Attach l1(4), advance l1
  Result: dummy->1->1->2->3->4, l1 = null, l2 = 4

Loop ends, attach remaining l2
Final: dummy->1->1->2->3->4->4

Complexity Analysis #

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) - We only use a constant amount of extra space for pointers. We’re not creating new nodes, just rewiring existing ones.

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. We can attach the entire remaining list in one operation.

4. In-Place Merging: The solution doesn’t create new nodes; it rewires existing nodes’ pointers, making it memory efficient.

5. Comparison Logic: The condition l1.val <= l2.val ensures stability—when values are equal, we take from the first list, though either choice maintains correctness for this problem.

Connection to Merge Sort #

This problem serves as an excellent foundation for understanding merge sort for linked lists. The merge operation is the core building block of merge sort, where you recursively split the list in half and then merge the sorted halves back together.

Conclusion #

Merging two sorted linked lists is a fundamental algorithm that demonstrates important linked list manipulation techniques. The solution elegantly combines the dummy node pattern with two-pointer traversal to achieve optimal time and space complexity. Understanding this problem is essential for tackling more complex linked list and sorting algorithms.