AlgoScope

List Pointer Puzzles

A singly linked list can only be walked forwards, one node at a time, so the classic puzzles are all about walking cleverly instead of storing things. To read a list backwards, reverse half of it in place and put it back afterwards. To find where two lists merge without measuring them, let each pointer walk its own list and then the other one: both cover the same total distance and arrive at the shared node together. To remove a cycle, the slow and fast meeting point plus a walk from the head lands on the loop's entry, and one lap round the loop finds the arrow to cut. Each is O(n) time with a constant number of pointers.

The player

Intersection of two lists.123956paheadBpb

List A (top) and list B (bottom) run into the same tail, so from some node on they are one list. Find the first shared node without knowing either length: walk pa down A and pb down B, and when a pointer runs off the end, restart it at the other list's head. Both then travel lenA + lenB and arrive at the shared node in step, or at null together.

Check your understanding

The player pauses before each decision in this run and asks what happens next. Here are all 3, with their answers.

  1. pb has run off the end. Where does it go?

    • To the other list's head
    • Back to its own head
    • It stops

    Answer: To the other list's head. Switching lists once makes both pointers cover both lengths.

  2. pa has run off the end. Where does it go?

    • To the other list's head
    • Back to its own head
    • It stops

    Answer: To the other list's head. Switching lists once makes both pointers cover both lengths.

  3. Both pointers have switched lists and walked the same distance. What happens on this step?

    • They meet at 5
    • They keep going
    • One reaches null

    Answer: They meet at 5. Both have now walked lenA + lenB steps, so they are aligned.

How it runs, step by step

  1. List A (top) and list B (bottom) run into the same tail, so from some node on they are one list. Find the first shared node without knowing either length: walk pa down A and pb down B, and when a pointer runs off the end, restart it at the other list's head. Both then travel lenA + lenB and arrive at the shared node in step, or at null together.

    Intersection of two lists.

  2. pa moves to 2. pb moves to 5.

  3. pa moves to 3. pb moves to 6.

  4. pa moves to 5. pb moves to null.

  5. pa moves to 6. pb ran off the end of B, so it restarts at A's head, 1.

  6. pa moves to null. pb moves to 2.

  7. pa ran off the end of A, so it restarts at B's head, 9. pb moves to 3.

  8. pa moves to 5. pb moves to 5. They point at the same node: 5 is where the lists join.

  9. The lists intersect at 5, found after 7 steps: each pointer walked its own list (5 and 3 nodes), stepped onto null, and walked the other list up to the join. No lengths were measured and no extra space used.

    Intersection at 5.

The code

List Pointer Puzzles, in Python

def is_palindrome(head):
    slow, fast = head, head
    while fast and fast.next:                              # slow: second half
        slow, fast = slow.next, fast.next.next
    second, first = reverse(slow), head
    same = True
    while second is not None:
        if first.value != second.value:
            same = False
        first, second = first.next, second.next
    reverse(slow)                                          # put the list back as it was
    return same

def intersection(a, b):
    pa, pb = a, b
    while pa is not pb:                                    # both None also ends the loop
        pa = b if pa is None else pa.next                  # at the end, switch to the other head
        pb = a if pb is None else pb.next
    return pa                                              # after lenA + lenB steps they line up

def remove_cycle(head):
    slow, fast = head, head
    while True:                                            # do-while: step first, test after
        slow = slow.next
        fast = fast.next.next if fast.next else None
        if fast is None or slow is fast:
            break
    if fast is None:                                       # fast fell off: no cycle
        return
    p = head                                               # head and meeting point walk together
    while p is not slow:                                   # they meet at the entry
        p, slow = p.next, slow.next
    tail = p                                               # once round the loop to the node before it
    while tail.next is not p:
        tail = tail.next
    tail.next = None                                       # cut the arrow that closes the loop

List Pointer Puzzles, in JavaScript

function isPalindrome(head) {
  let slow = head;
  let fast = head;
  while (fast?.next != null) {                               // slow: second half
    slow = slow.next;
    fast = fast.next.next;
  }
  let second = reverse(slow);
  let first = head;
  let same = true;
  while (second != null) {
    if (first.value !== second.value) same = false;
    first = first.next;
    second = second.next;
  }
  reverse(slow);                                             // put the list back as it was
  return same;
}

function intersection(a, b) {
  let pa = a;
  let pb = b;
  while (pa !== pb) {                                        // both null also ends the loop
    pa = pa == null ? b : pa.next;                           // at the end, switch to the other head
    pb = pb == null ? a : pb.next;
  }
  return pa;                                                 // after lenA + lenB steps they line up
}

function removeCycle(head) {
  let slow = head;
  let fast = head;
  do {                                                       // step first, test after
    slow = slow.next;
    fast = fast.next?.next ?? null;
  } while (fast != null && slow !== fast);
  if (fast == null) return;                                  // fast fell off: no cycle
  let p = head;                                              // head and meeting point walk together
  while (p !== slow) {                                       // they meet at the entry
    p = p.next;
    slow = slow.next;
  }
  let tail = p;                                              // once round the loop to the node before it
  while (tail.next !== p) tail = tail.next;
  tail.next = null;                                          // cut the arrow that closes the loop
}

List Pointer Puzzles, in Kotlin

fun isPalindrome(head: Node?): Boolean {
    var slow = head; var fast = head
    while (fast?.next != null) { slow = slow!!.next; fast = fast.next!!.next }   // slow: second half
    var second = reverse(slow); var first = head
    var same = true
    while (second != null) {
        if (first!!.value != second.value) same = false
        first = first.next; second = second.next
    }
    reverse(slow)                                              // put the list back as it was
    return same
}

fun intersection(a: Node?, b: Node?): Node? {
    var pa = a; var pb = b
    while (pa !== pb) {                                        // both null also ends the loop
        pa = if (pa == null) b else pa.next                    // at the end, switch to the other head
        pb = if (pb == null) a else pb.next
    }
    return pa                                                  // after lenA + lenB steps they line up
}

fun removeCycle(head: Node) {
    var slow: Node? = head; var fast: Node? = head
    do { slow = slow!!.next; fast = fast!!.next?.next } while (fast != null && slow !== fast)
    if (fast == null) return                                   // fast fell off: no cycle
    var p: Node = head                                         // head and meeting point walk together
    while (p !== slow) { p = p.next!!; slow = slow!!.next }   // they meet at the entry
    var tail = p                                               // once round the loop to the node before it
    while (tail.next !== p) tail = tail.next!!
    tail.next = null                                           // cut the arrow that closes the loop
}

Write it yourself

Define isPalindromeList(values) and return true when the list reads the same in both directions. It runs in your browser against this lesson's own 2 examples.

// Find the middle with a fast and a slow pointer, reverse the second half, and walk the two halves together.function isPalindromeList(values) { return false;}
6 linesTab indents. Escape, then Tab, leaves the editor. Ctrl-Enter runs (Cmd-Enter on a Mac).

    Remember

    • Palindrome: slow and fast to the middle, reverse the second half, compare front against back, reverse it back.
    • Intersection: walk pa down A then B and pb down B then A. They meet at the shared node after lenA + lenB steps, or at null together.
    • Remove cycle: after slow and fast meet, walk from the head and the meeting point together to the entry, then once round the loop to cut the arrow before it.

    Where this is used

    Repairing a FAT filesystemFilesystems

    On a FAT volume a file is literally a singly linked list: the directory entry names the first cluster and the file allocation table says which cluster follows each one. Corruption produces exactly these two puzzles, and fsck.fat lists both as things it fixes - a cluster chain that contains a loop, and two or more files that share the same clusters, which is two lists merging into a common tail. There is no way to jump into the middle of a file, so the chain is walked one link at a time and the loop has to be noticed before the walk becomes endless.

    Reversing the kernel's lockless listOperating systems

    Linux's llist is a lock-free singly linked stack: producers push with llist_add and a consumer takes the whole chain in one atomic swap. llist.h spells out what that costs - the entries come back newest first, and if you want to walk them oldest to newest you have to reverse the chain yourself. llist_reverse_order in lib/llist.c is exactly the three-pointer walk this lesson's reverse() does: hold the node, remember its next, point it back at the new head, move on. Callers can be in interrupt or NMI context, where allocating a scratch array to sort the chain into is not available, so the rewiring happens in place.

    Bitcoin Core finding a fork pointDistributed systems

    A block header stores the hash of its parent, so a chain is a singly linked list that can only be walked backwards toward the genesis block. Before switching to a competing chain a node has to find the last block the two share, which is the intersection problem: Bitcoin Core's LastCommonAncestor drops the taller chain down to the other's height first and then steps both back in lockstep. That is the variant you use when the lengths are already known, and the head-swapping walk in this lesson is what you do when they are not.

    Marking a heap with no spare memoryMemory management

    A tracing collector normally marks live objects using an explicit stack of nodes still to visit, but a collector runs precisely when memory has run out, so that stack is the one thing it may not be able to afford. The Deutsch-Schorr-Waite algorithm reverses each pointer as it descends into an object, so the route back to the root is held in the heap itself, and puts every pointer back on the way up. That is the same move as reversing half a list to read it backwards and reversing it again to leave no trace, which is why early Lisp and embedded collectors used it.

    Why it works this way

    Why the intersection walk has to step through null

    Each pointer walks one list and then the other, so both cover the same total distance, and the null at the end of each list counts as one of those steps. The classic bug is to write the switch as "if the next node is null, jump to the other head", which skips null entirely: two lists that never merge then chase each other forever, because the pointers are only ever equal at a shared node and there is none. Landing on null is what lets both pointers be null on the same step, and null matching null is what ends the loop.

    Why walking from the head lands on the loop's entry

    Call L the number of steps from the head to the entry, C the length of the loop, and say the pointers meet k steps into it. Slow has walked L + k and fast exactly twice that, and fast's extra distance is a whole number of laps, so L + k = mC and therefore L = mC - k. The distance forward from the meeting point round to the entry is C - k plus m - 1 more laps, which is the same mC - k. The two walks are the same length, so a pointer from the head and a pointer from the meeting point arrive together.

    The palindrome check leaves the list broken while it runs

    Reversing the second half rewires real nodes: mid-check the middle node's next is null and the back half runs the other way, which is why the code reverses a second time instead of just returning. It is also why the compare loop is driven by second rather than first. The front half still runs into the reversed region and is never the shorter of the two, so stopping when first runs out reads second one step after it has already hit null on an even-length list. If anything else can see the list while this runs, copy the values into an array instead.

    Why the cycle loop is a do-while, and why fast steps by two

    slow and fast both start at the head, so a plain while (slow !== fast) would exit before either has moved. The do-while forces the first step. A stride of two makes the gap between the pointers shrink by exactly one node per round once both are inside the loop, so it has to reach zero and they cannot step over each other. A stride of three shrinks the gap by two, and on a loop of even length with an odd gap that never reaches zero. Both levels of fast.next?.next need the null check: guarding only one crashes at the end of a cycle-free list with an odd number of nodes.

    Read more

    Next up

    Reorder List

    Middle by slow and fast, reverse the second half, weave first and second alternately.

    Next lesson: Reorder List