Merge Two Sorted Lists | Linked List Merge | Linked List

Overview

Merging two sorted linked lists means combining them into one sorted list by repeatedly taking the smaller of the two current heads and appending it to the result. You only change pointers; no new nodes are created (unless you choose to copy). This pattern is the core of merge sort on linked lists and appears in "merge k sorted lists" as well.

Key idea: Both lists are already sorted, so the overall minimum is always at one of the two heads. Compare the two heads, append the smaller, advance that list's pointer, and repeat until one list is exhausted; then attach the rest of the other list.

When to Use

Merge two sorted lists — classic problem and building block.
Merge sort on linked list — split (e.g. with fast/slow), sort halves recursively, then merge.
Merge k sorted lists — repeatedly merge two (or use a min-heap of head nodes).
Reusable helper — many list problems reduce to "merge two sorted segments."

How It Works

Use a dummy head so you have a single place to append; no "first node" branch.
Keep a tail pointer at the last node of the merged list (initially the dummy).
While both lists are non-empty: compare l1.val and l2.val, set tail.next to the smaller node, advance that list's pointer and set tail = tail.next.
When one list is exhausted, set tail.next to the remaining list (the other head).
Return dummy.next.

Example 1: Merge Two Sorted Lists (Iterative)

Problem: Merge two sorted linked lists and return the head of the merged list. Create the list by changing pointers only.

function mergeTwoLists(l1: ListNode | null, l2: ListNode | null): ListNode | null {
  const dummy = new ListNode(-1);
  let 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;
}

Time: O(n + m), Space: O(1).

Example 2: Merge Two Sorted Lists (Recursive)

Problem: Same; solve recursively.

function mergeTwoLists(l1: ListNode | null, l2: ListNode | null): ListNode | null {
  if (l1 === null) return l2;
  if (l2 === null) return l1;
  if (l1.val <= l2.val) {
    l1.next = mergeTwoLists(l1.next, l2);
    return l1;
  }
  l2.next = mergeTwoLists(l1, l2.next);
  return l2;
}

Time: O(n + m), Space: O(n + m) for the call stack.

Example 3: Merge Sort on Linked List (Split + Merge)

Problem: Sort a linked list in O(n log n) time and O(log n) space (stack).

Split with fast/slow to find the middle, recursively sort the two halves, then merge with the two-sorted merge.

function sortList(head: ListNode | null): ListNode | null {
  if (head === null || head.next === null) return head;
  let slow: ListNode | null = head;
  let fast: ListNode | null = head;
  let prev: ListNode | null = null;
  while (fast !== null && fast.next !== null) {
    prev = slow;
    slow = slow!.next;
    fast = fast.next.next;
  }
  prev!.next = null;
  const left = sortList(head);
  const right = sortList(slow);
  return mergeTwoLists(left, right);
}

Time: O(n log n), Space: O(log n) stack.

Example 4: Merge Two Lists In-Place (No Dummy, Reuse Nodes)

If you cannot use a dummy (e.g. must not allocate), you can still merge by choosing the smaller head as the result head, then advancing and appending from the other list. The iterative version with a dummy is usually clearer and preferred.

Edge Cases

One list empty — Return the other list. The while loop does not run; tail.next = l1 ?? l2 handles it.
Both empty — Return null; dummy.next stays null.
One list much longer — After the loop, one pointer is null; attaching the other gives the rest in one step.

Common Mistakes

Forgetting to advance tail — Always set tail = tail.next after appending.
Returning dummy — Return dummy.next, not dummy.
Losing the rest — After the loop, set tail.next to whichever list is still non-null.
Strict vs non-strict comparison — Use “<=” so when values are equal, the first list is chosen consistently (stable merge).

Time and Space Complexity

Time: O(n + m) — each node is visited once.
Space: O(1) iterative with dummy; O(n + m) recursive stack.

Summary

Merge two sorted: dummy + tail; while both non-null, append the smaller and advance; then attach the remainder; return dummy.next.
Foundation for Sort List (merge sort) and Merge K Sorted Lists.

See Dummy Head for the append pattern and Fast and Slow Pointers for splitting in merge sort.

Merging Two Sorted Lists