3.7 Merge Two Sorted Lists

Merging combines two sorted singly linked lists into one sorted list by relinking nodes. The operation does not create new nodes. It reuses existing nodes and preserves their order.

Problem

Given two lists l1 and l2, both sorted in non-decreasing order, produce a single sorted list.

l1: a1 -> a2 -> ...
l2: b1 -> b2 -> ...

Return a list that contains all nodes from both inputs, ordered.

Sentinel-Based Solution

A sentinel simplifies head handling and ensures uniform insertion.

dummy = new Node()
tail = dummy

p = l1
q = l2

while p != null and q != null:
  if p.value <= q.value:
    tail.next = p
    p = p.next
  else:
    tail.next = q
    q = q.next

  tail = tail.next

if p != null:
  tail.next = p
else:
  tail.next = q

return dummy.next

Invariant

At each step:

• dummy.next ... tail is a fully merged sorted prefix
• p and q point to the remaining suffixes
• no nodes are duplicated or lost

The algorithm advances exactly one node per iteration.

Execution Trace

Given:

l1: 1 -> 3 -> 5
l2: 2 -> 4 -> 6

Steps:

1 chosen -> tail = 1
2 chosen -> tail = 2
3 chosen -> tail = 3
4 chosen -> tail = 4
...

Final:

1 -> 2 -> 3 -> 4 -> 5 -> 6

Stability

The condition

if p.value <= q.value

preserves stability. When values are equal, nodes from l1 appear before nodes from l2, maintaining their original relative order.

Complexity

Each node is visited once.

Recursive Variant

merge(l1, l2):
  if l1 == null:
    return l2
  if l2 == null:
    return l1

  if l1.value <= l2.value:
    l1.next = merge(l1.next, l2)
    return l1
  else:
    l2.next = merge(l1, l2.next)
    return l2

This form is concise but uses O(n + m) stack space.

Merge k Lists

Repeated merging extends to k lists. A simple method merges lists pairwise.

while more than one list:
  merge pairs

A more efficient approach uses a min-heap.

push heads of all lists into heap

while heap not empty:
  node = extract min
  append node to result
  if node.next != null:
    push node.next

Time complexity becomes O(N log k), where N is the total number of nodes.

Common Failure Modes

• Forgetting to advance tail after attaching a node
• Losing the remainder by not linking the leftover list
• Returning dummy instead of dummy.next
• Breaking stability by using < instead of <=
• Reassigning next incorrectly and creating cycles

Key Insight

Merging is a controlled selection process. At each step, the smallest available node is chosen and appended to the result. The sentinel ensures that the append operation is uniform from the first node to the last.

This pattern appears repeatedly in divide-and-conquer algorithms, especially merge sort, and in multi-stream processing where ordered data must be combined efficiently.