# 3.22 Edge Cases

Edge cases are inputs that sit near the boundary of an algorithm's assumptions. In linked list problems, these cases usually involve empty lists, one-node lists, changes at the head, changes at the tail, repeated values, cycles, shared nodes, or invalid positions.

A linked list algorithm is often correct for the middle of the list before it is correct for the boundaries. This section gives a checklist for finding and handling those boundaries.

## Empty List

The empty list has no nodes.

```text id="x5k2m9"
head = null
```

Every traversal must check this case before reading `head.value` or `head.next`.

```text id="r8q1v6"
if head == null:
  return null
```

Operations such as search, reverse, merge, and split should define clear behavior on an empty input.

```text id="k4m7z2"
reverse(null) = null
merge(null, list) = list
split(null) = (null, null)
```

## One-Node List

A one-node list is both head and tail.

```text id="p9w3c5"
head -> null
```

Many algorithms should return the same node unchanged.

```text id="y6n4b8"
if head == null or head.next == null:
  return head
```

This guard appears in reversal, merge sort, palindrome checks, and middle-based splitting.

## Two-Node List

A two-node list exposes off-by-one errors.

```text id="q2d8h1"
a -> b -> null
```

Examples:

```text id="z7c5v2"
reverse: b -> a -> null
split halves: a -> null, b -> null
middle second convention: b
middle first convention: a
```

Testing only empty, one-node, and long lists can miss bugs in this case.

## Deleting the Head

Without a dummy node, deleting the head requires direct update of `head`.

```text id="v5t8r3"
head = head.next
```

With a dummy node, the same deletion rule works everywhere.

```text id="m1h9k6"
dummy.next = head
prev = dummy
cur = head
```

After deletion, return:

```text id="f3n7x4"
dummy.next
```

The common error is changing a local pointer but forgetting to update the external head reference.

## Deleting the Tail

The tail is the last node. In a singly linked list, deleting it requires finding its predecessor.

```text id="h6q2n9"
prev.next = null
```

If the structure stores a `tail` pointer, update it too.

```text id="c8v1m5"
tail = prev
```

If the deleted node was the only node, both `head` and `tail` become `null`.

## Inserting at the Head

Insert before the first node by updating `head`.

```text id="g4p6s1"
new.next = head
head = new
```

With a dummy node:

```text id="b9x2t7"
new.next = dummy.next
dummy.next = new
```

Again, return `dummy.next`.

## Inserting at the Tail

Insert after the last node by setting its `next`.

```text id="n3r8w4"
tail.next = new
tail = new
new.next = null
```

If the list was empty, both `head` and `tail` must point to `new`.

## Repeated Values

Repeated values can cause algorithms to remove too little or too much.

For example:

```text id="u7k5q2"
1 -> 2 -> 2 -> 2 -> 3 -> null
```

Deleting all `2` values requires keeping the predecessor fixed while matching nodes are removed.

```text id="d5m8v1"
if cur.value == target:
  prev.next = cur.next
  cur = prev.next
else:
  prev = cur
  cur = cur.next
```

Do not advance `prev` after a deletion.

## All Nodes Removed

Deletion by predicate may remove every node.

```text id="s2c9p5"
2 -> 2 -> 2 -> null
```

After deletion, the result must be:

```text id="k7v3r1"
null
```

A dummy node handles this case cleanly because `dummy.next` may become `null`.

## No Nodes Removed

The opposite case should preserve the original structure.

```text id="h1q6m4"
1 -> 3 -> 5 -> null
```

If deleting even values, the result is unchanged. The algorithm must still advance correctly and terminate.

## Invalid Position

Position-based operations need a defined policy.

Examples:

```text id="p4b8z6"
insert at position greater than length
delete at position greater than or equal to length
delete nth from end when n > length
```

Possible policies:

| Policy | Behavior                                     |
| ------ | -------------------------------------------- |
| Reject | return error                                 |
| Clamp  | insert at nearest valid boundary             |
| Ignore | return list unchanged                        |
| Extend | create missing positions, rarely appropriate |

The policy should be explicit before implementation.

## Cycles

Many linked list algorithms assume that traversal reaches `null`. If the input may contain a cycle, ordinary traversal can loop forever.

```text id="w6m9x2"
while cur != null:
  cur = cur.next
```

Cycle-sensitive code should detect cycles first or maintain a visited set.

## Shared Nodes

Two lists may share a suffix.

```text id="z1r7c8"
l1: a -> b -> c -> d
l2: x -> y -> c -> d
```

Mutating the shared suffix through one list changes the other. Algorithms that promise not to modify inputs should copy nodes rather than relink them.

## Checklist

Before accepting a linked list solution, test these cases:

| Case                | Example                   |
| ------------------- | ------------------------- |
| Empty               | `null`                    |
| One node            | `a`                       |
| Two nodes           | `a -> b`                  |
| Delete head         | remove `a` from `a -> b`  |
| Delete tail         | remove `b` from `a -> b`  |
| Insert at head      | insert before `a`         |
| Insert at tail      | insert after `b`          |
| Consecutive matches | `1 -> 2 -> 2 -> 3`        |
| All removed         | `2 -> 2 -> 2`             |
| None removed        | `1 -> 3 -> 5`             |
| Odd length          | `a -> b -> c`             |
| Even length         | `a -> b -> c -> d`        |
| Invalid position    | `k > length`              |
| Cycle               | `a -> b -> c -> b`        |
| Shared suffix       | two heads reach same tail |

## Key Insight

Edge cases are not exceptional in linked list algorithms. They are consequences of pointer structure. A robust solution defines behavior at the boundaries first, then uses sentinels, invariants, and clear ownership rules to make the general case and the boundary case follow the same logic.