# 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:

```text id="k3m4zs"
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.

```text id="m7k2qp"
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.

```text id="x9b7cq"
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:

```text id="y1n2q4"
l1: a -> c -> e
l2: b -> d -> f
```

result:

```text id="u3t8vz"
a -> b -> c -> d -> e -> f
```

This pattern requires saving `next` before relinking.

## Zip Merge (Pairwise)

Combine nodes in pairs from two lists.

```text id="h6k5jz"
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.

```text id="z2p6wl"
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.

```text id="u9y2nt"
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.

```text id="k8x2fj"
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:

```text id="r0j6hm"
if p.value <= q.value:
```

ensures stable behavior.

## Complexity Summary

| Pattern            |       Time | Space |
| ------------------ | ---------: | ----: |
| Two-list merge     |   O(n + m) |  O(1) |
| Alternating merge  |   O(n + m) |  O(1) |
| Zip merge          |   O(n + m) |  O(1) |
| Conditional merge  |   O(n + m) |  O(1) |
| k-way merge (heap) | O(N log k) |  O(k) |
| Concatenation      |       O(n) |  O(1) |

## 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.