3.9 Merge Patterns

Merging is a family of constructions that combine multiple linked lists into one or more output lists while preserving structural invariants. Unlike simple two-list merge, these patterns generalize to conditional routing, alternating consumption, or multi-way combination.

Problem

Given one or more input lists, construct an output list by selecting nodes according to a rule, without allocating new nodes.

Typical rules include:

merge two sorted lists
merge k sorted lists
alternate merge
conditional merge by predicate
zip merge

All variants share the same risk: losing nodes or creating cycles when links are reassigned incorrectly.

Core Pattern

Use a sentinel and a moving tail.

dummy = new Node()
tail = dummy

At each step:

• choose a node from one input
• attach it to tail.next
• advance tail

This pattern isolates construction from selection logic.

Alternating Merge

Alternate nodes from two lists.

dummy = new Node()
tail = dummy

p = l1
q = l2

take_p = true

while p != null or q != null:
  if take_p and p != null:
    next = p.next
    tail.next = p
    tail = p
    p = next
  elif q != null:
    next = q.next
    tail.next = q
    tail = q
    q = next

  take_p = not take_p

return dummy.next

For:

l1: a -> c -> e
l2: b -> d -> f

result:

a -> b -> c -> d -> e -> f

This pattern requires saving next before relinking.

Zip Merge (Pairwise)

Combine nodes in pairs from two lists.

dummy = new Node()
tail = dummy

p = l1
q = l2

while p != null and q != null:
  next_p = p.next
  next_q = q.next

  tail.next = p
  p.next = q
  tail = q

  p = next_p
  q = next_q

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

return dummy.next

This pattern preserves adjacency relationships between paired elements.

Conditional Merge

Select nodes from either list based on a predicate.

dummy = new Node()
tail = dummy

p = l1
q = l2

while p != null or q != null:
  if choose_from_p(p, q):
    next = p.next
    tail.next = p
    tail = p
    p = next
  else:
    next = q.next
    tail.next = q
    tail = q
    q = next

return dummy.next

The function choose_from_p encodes selection logic. For sorted merge, it compares values. For other uses, it may depend on external constraints.

Merge k Sorted Lists

Use a priority queue (min-heap) to select the smallest current node across k lists.

heap = empty

for each list head:
  if head != null:
    push head into heap

dummy = new Node()
tail = dummy

while heap not empty:
  node = extract_min(heap)

  tail.next = node
  tail = node

  if node.next != null:
    push node.next into heap

return dummy.next

Time complexity is O(N log k), where N is total nodes.

In-Place Concatenation

When no ordering constraint exists, merging reduces to concatenation.

if l1 == null:
  return l2

cur = l1
while cur.next != null:
  cur = cur.next

cur.next = l2
return l1

This is O(n) for the first list.

Stability

A merge is stable if nodes from each input retain their original relative order. Stability depends on always choosing from the same list first when equal conditions occur.

For example:

if p.value <= q.value:

ensures stable behavior.

Complexity Summary

Common Failure Modes

• Not saving next before reassigning node.next
• Forgetting to advance tail
• Creating cycles by linking a node twice
• Dropping remaining nodes after loop
• Returning the sentinel instead of dummy.next

Key Insight

Merging is selection plus attachment. The selection rule determines which node is chosen next. The attachment rule must preserve reachability and ordering. A sentinel node isolates these concerns and allows the algorithm to focus on correct selection.

These patterns generalize to streams, iterators, and external data sources where elements arrive incrementally but must be combined under strict ordering or structural constraints.