7.3 Merge Two Sorted Lists

7.3.1 Problem Metadata

7.3.2 Description

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

7.3.3 Examples

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

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

7.3.4 Constraints

  • The number of nodes in both lists is in the range [0, 50]
  • -100 <= Node.val <= 100
  • Both lists are sorted in non-decreasing order

7.3.5 Solution - Iterative Merge

7.3.5.1 Walkthrough

This solution uses a dummy head and tail pointer to iteratively build the merged list by always appending the smaller node.

Core Strategy:

  1. Create a dummy node as the anchor for the result list
  2. Compare the current nodes of both lists
  3. Append the smaller one to the result and advance that pointer
  4. When one list is exhausted, append the remaining list directly

Example: Merge [1,2,4] and [1,3,4]:

Step 1: Compare 1 vs 1 → take l1's 1, result: [1]
Step 2: Compare 2 vs 1 → take l2's 1, result: [1,1]
Step 3: Compare 2 vs 3 → take l1's 2, result: [1,1,2]
Step 4: Compare 4 vs 3 → take l2's 3, result: [1,1,2,3]
Step 5: Compare 4 vs 4 → take l1's 4, result: [1,1,2,3,4]
Step 6: l1 exhausted → append l2's remaining [4]
Final: [1,1,2,3,4,4]

7.3.5.2 Analysis

  • Time Complexity: O(m + n) - Each node is visited exactly once
  • Space Complexity: O(1) - Only pointer variables used (reusing existing nodes)

7.3.5.3 Implementation Steps

  1. Create a dummy node and a tail pointer.
  2. While both lists have nodes, compare and append the smaller one.
  3. Append the remaining non-empty list.
  4. Return dummy.next.

7.3.5.4 Code - Java

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode tail = dummy;
    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) {
            tail.next = l1;
            l1 = l1.next;
        } else {
            tail.next = l2;
            l2 = l2.next;
        }
        tail = tail.next;
    }
    tail.next = (l1 != null) ? l1 : l2;
    return dummy.next;
}