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

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

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

```text id="l4s5w1"
l1: 1 -> 3 -> 5
l2: 2 -> 4 -> 6
```

Steps:

```text id="4o9v67"
1 chosen -> tail = 1
2 chosen -> tail = 2
3 chosen -> tail = 3
4 chosen -> tail = 4
...
```

Final:

```text id="u6r8xh"
1 -> 2 -> 3 -> 4 -> 5 -> 6
```

## Stability

The condition

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

| Metric | Value    |
| ------ | -------- |
| Time   | O(n + m) |
| Space  | O(1)     |

Each node is visited once.

## Recursive Variant

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

```text id="6t5z3g"
while more than one list:
  merge pairs
```

A more efficient approach uses a min-heap.

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