Merge Two Sorted Lists

Problem Statement

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.

Return the head of the merged linked list.

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]

Approach: Dummy Node & Iteration

We can solve this problem elegantly by using a Dummy Node. This is a common Linked List technique that acts as a placeholder head for the new list we are building. It helps us avoid tricky edge cases (like when the first element we need to insert is the head itself).

1. Create a dummy node (e.g., new ListNode(-1)).
2. Create a tail pointer, initially pointing to the dummy node. We will use tail to build the new merged list node by node.
3. Loop while both list1 and list2 are not null:
   • Compare the values of the current nodes in list1 and list2.
   • Point tail.next to the node with the smaller value.
   • Advance the pointer of the chosen list (list1 = list1.next or list2 = list2.next).
   • Advance the tail pointer (tail = tail.next).
4. Once the loop ends, at least one of the lists has been fully traversed. The other list may still have nodes left over.
   • Because the original lists were already sorted, any remaining nodes are already in their correct sorted order.
   • Simply point tail.next to the remaining non-null list.
5. Return dummy.next. This skips the initial placeholder node and returns the true head of the newly merged list.

Solution

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode}
 */
function mergeTwoLists(list1, list2) {
    // Create a dummy node to act as the head of the merged list
    let dummy = new ListNode(-1);
    let tail = dummy;
    
    // Iterate while both lists have nodes
    while (list1 !== null && list2 !== null) {
        if (list1.val < list2.val) {
            tail.next = list1;
            list1 = list1.next;
        } else {
            tail.next = list2;
            list2 = list2.next;
        }
        tail = tail.next;
    }
    
    // Append any remaining nodes from list1 or list2
    if (list1 !== null) {
        tail.next = list1;
    } else if (list2 !== null) {
        tail.next = list2;
    }
    
    // Return the actual head of the merged list (skipping the dummy)
    return dummy.next;
}

Complexity Analysis

• Time Complexity: $O(m + n)$ where $m$ and $n$ are the lengths of list1 and list2. In the worst case, we traverse all nodes in both lists exactly once.
• Space Complexity: $O(1)$. We are only modifying existing pointers (splicing the lists together) and using a single dummy node, so no extra memory is allocated for the list structures.