Skip to content

Linked List Pointer Choreography

Problem

When you see linked lists and the task mentions "from end", "middle", "cycle", "palindrome", or "reverse"

Strategy: Linked List Pointer Choreography

  • Think about this
    • Use pointer choreography, not extra arrays, unless follow-up allows it.
    • Standard templates:
      • dummy node for deletion/merge
      • slow/fast for middle or cycle
      • iterative reverse with prev, cur, nxt
      • reverse second half, then compare
    • If asked to delete with only the node, overwrite with next then bypass next.
  • Avoid this
    • Do not try to find a previous node you cannot access.
    • Do not lose the rest of the list by rewiring before saving next.
    • Do not compare node values for cycle detection; compare node identity.
    • Do not mutate node schema by inventing fields like prev.
  • Tell this to the interviewer
    • Say exactly what each pointer means.
    • Use a dummy node whenever head deletion or merge head special-casing appears.
  • See these problems