Linked Lists Without Losing the Rest

An array is memory you rent; a linked list is memory you wire. Each node carries a pointer to the next, and every algorithm on the structure is a discipline about those pointers: turn one around without orphaning everything behind it, walk at two speeds to find a loop, splice two lists without special-casing the first stitch. The structure looks simple because its difficulty is not in syntax — it is in not losing things.

The one rule: hold the rest before you turn

Reversal is the canonical question because it fails in the canonical way. Three variables do the whole job — where you came from, where you are, and what you must not lose:

export function reverseList(head: ListNode | undefined): ListNode | undefined {
  let previous: ListNode | undefined = undefined
  let current: ListNode | undefined = head

  while (current !== undefined) {
    const next: ListNode | undefined = current.next // hold the rest
    current.next = previous // turn the pointer around
    previous = current // step forward
    current = next
  }
  return previous
}

Read the loop as one sentence per line: save the tail, point backwards, advance the frontier, follow the saved tail. Swap the first two lines and the list after current becomes unreachable the instant you write current.next = previous — not an error, just memory nobody can visit anymore. When the loop ends, current is undefined and previous is the last node you touched: the new head. That is the entire proof, and it is why the return is previous — the variable people try to return is head, which by then is the tail.

while (current !== undefined) {
  const next: ListNode | undefined = current.
  current.next = previous
  previous = current
  current = next
}

The tortoise and the hare

A corrupted list loops back on itself, and you cannot see that from the shape — you can only walk it. Two pointers at different speeds settle the question with constant memory: in a loop, the fast runner laps the slow one, so they must meet; on a straight list, the fast runner reaches the end first.

export function hasCycle(head: ListNode | undefined): boolean {
  let tortoise = head
  let hare = head

  while (hare !== undefined && hare.next !== undefined) {
    tortoise = tortoise?.next
    hare = hare.next.next
    if (tortoise === hare) return true
  }
  return false
}

The loop's condition is the part that carries the safety: the hare takes two steps (hare.next.next), so before every leap both hare and hare.next must exist — the check is not defensive decoration, it is what keeps the second step from reading through undefined. The meeting itself needs no cleverness: each iteration inside the loop changes the gap between the runners by exactly one, so the gap cycles through every value including zero. The elegance people remember is really just arithmetic.

while (hare !== undefined && hare. !== undefined) {
  tortoise = tortoise?.next
  hare = hare.next.next
  if (tortoise === hare) return true
}

The dummy head: deleting the first case

Merging two sorted lists interleaves nodes by value, and the very first stitch is special — somebody has to become the head. A throwaway node absorbs the specialness: the loop always writes tail.next and never asks whether the list has started.

export function mergeSorted(
  a: ListNode | undefined,
  b: ListNode | undefined
): ListNode | undefined {
  const head: ListNode = { value: Number.NaN }
  let tail = head

  while (a !== undefined && b !== undefined) {
    if (a.value <= b.value) {
      tail.next = a
      a = a.next
    } else {
      tail.next = b
      b = b.next
    }
    tail = tail.next as ListNode
  }
  tail.next = a ?? b // the survivor is already sorted and already linked

  return head.next
}

The last line before the return is where merges go to die: the loop ends when one list is exhausted, not both, and the survivor's remainder is sorted and self-linked — attach it whole or it vanishes. Tests built from equal-length lists never catch the omission, because equal lists exhaust together. This is worth saying as a rule: a merge helper is only as tested as its unequal inputs.

How to debug a walk

Draw it. A linked list is one of the two structures (the other is the tree) where paper beats print: boxes, arrows, and a finger for each variable. Move the fingers line by line, and the orphaning step is visible as an arrow you erase before drawing its replacement. When you must print, print the chain, not the node — for (let n = head; n; n = n.next) out.push(n.value) — and give the walk a step limit: a debug loop that itself runs forever on a cyclic list teaches you nothing except that the list is cyclic (which the tortoise already tells you in O(1) memory). For cycle tests, build the loop by hand — create the nodes, then assign tail.next = someEarlierNode — because a fixture that generates a cycle usually generates the wrong one.

Where this bites

• Turning the pointer before saving the tail. current.next = previous first orphans everything after current; the algorithm then reverses a list of length one, repeatedly. Counter: the hold line and the turn line are one ordered unit — save, then turn — the same discipline as look-before-write in the hash map chapter.
• Returning the old head. After reversal the head is the tail, and returning it hands back a one-node list that looks eerily plausible. Counter: return the variable the loop's invariant names — the last node turned around, not the node you were given.
• The hare's unguarded second step. hare.next.next on a one-node remainder reads a field of undefined; the crash looks like a null-deref "sometimes" because it depends on parity. Counter: the loop condition checks both hops the hare is about to take — write it before writing the leap.
• A merge that forgets the survivor. Equal-length tests pass, unequal inputs silently lose the longer list's tail — the review exercise in this concept's practice is exactly this defect. Counter: after the loop, attach a ?? b in one line; the remainder needs no iteration, one assignment is the whole stitch.