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.

head = null

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

if head == null:
  return null

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

reverse(null) = null
merge(null, list) = list
split(null) = (null, null)

One-Node List

A one-node list is both head and tail.

head -> null

Many algorithms should return the same node unchanged.

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.

a -> b -> null

Examples:

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.

head = head.next

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

dummy.next = head
prev = dummy
cur = head

After deletion, return:

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.

prev.next = null

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

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.

new.next = head
head = new

With a dummy node:

new.next = dummy.next
dummy.next = new

Again, return dummy.next.

Inserting at the Tail

Insert after the last node by setting its next.

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:

1 -> 2 -> 2 -> 2 -> 3 -> null

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

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.

2 -> 2 -> 2 -> null

After deletion, the result must be:

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.

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:

insert at position greater than length
delete at position greater than or equal to length
delete nth from end when n > length

Possible policies:

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.

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.

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:

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.