18. Merge Two Sorted Lists

Difficulty:EasyPattern:Dummy Head WeavingTime:O(n + m)Space:O(1)

You are given the heads of two sorted linked lists list1 and list2. Merge the two lists in a one sorted list.

How It Works & Algorithmic Design

Solves using Dummy Node Iterative Pointer Weaving:

Dummy Head: Create a dummy sentinel node and pointer tail = dummy.
Compare & Link (While list1 !== null and list2 !== null):
- If list1.val <= list2.val, set tail.next = list1 and list1 = list1.next.
- Else, set tail.next = list2 and list2 = list2.next.
- Advance tail = tail.next.
Attach Remainder: tail.next = list1 !== null ? list1 : list2.
Return: dummy.next holds the head of the newly merged sorted list.

Why This Approach Works Best

Sentinel dummy nodes remove edge-case code for initial head assignments, merging lists in $O(n + m)$ time and $O(1)$ extra space.

Example Walkthrough

Inputs: list1 = 1->2->4, list2 = 1->3->4

Two sorted lists.

Merge Trace: 1 (from l1) -> 1 (from l2) -> 2 (l1) -> 3 (l2) -> 4 (l1) -> 4 (l2)

Interleaves nodes in sorted order.

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

Single sorted merged list.

Answer: Merge sorted lists using dummy head

function mergeTwoLists(list1, list2) {
  const dummy = { val: 0, next: null };
  let tail = dummy;
  while (list1 && list2) {
    if (list1.val <= list2.val) {
      tail.next = list1; list1 = list1.next;
    } else {
      tail.next = list2; list2 = list2.next;
    }
    tail = tail.next;
  }
  tail.next = list1 || list2;
  return dummy.next;
}

💡 Weave node references in sorted order using a dummy sentinel node.

Key Takeaways

Dummy nodes clean up null edge checks for initial head pointers.
Reuses existing nodes without new memory allocation ($O(1)$ space).
Linear time complexity $O(n + m)$.