Topic notebook / 09
Linked lists & pointers
List nodes have identities and next pointers. Changing a link changes traversal order, not the value stored in the node.
What to look for
- Save the next link before overwriting it.
- Use stable node identities for duplicate values.
- Consider empty, singleton and cyclic structures.
Work through a question
6 availableTurn a Relay Chain Around
Build a singly linked relay chain from a JSON list of integer readings. Reverse its next pointers and return the readings reached from the new head. Node identity is its original index, even for equal readings.
Easy / Three-pointer reversal / interactiveDetect a Looping Relay
Starting at node 0, detect a repeated node by identity. Input is an acyclic JSON list, or {"values":[...],"cycle":null|index} linking the tail to an index, or {"values":[...],"next":[null|index,...]} specifying every pointer. Explicit-pointer nodes must all be reachable from node 0.
Easy / Floyd slow and fast pointers / interactiveJoin Two Ordered Relays
Build two nondecreasing singly linked chains from {"left":[...],"right":[...]}. Relink their existing nodes into one nondecreasing chain and return its readings. On equal values take the left node first.
Easy / Sentinel and two head pointers / interactiveJoin Several Ordered Relays
Build a chain for every row in a JSON list of sorted integer lists. Relink nodes into one sorted chain and return its readings. Heap ties use source index then original node position for deterministic identity order.
Hard / Heap of source heads / interactiveUnplug a Relay From the Tail
Build a nonempty singly linked chain from a JSON integer list. Given parameter n (1 through chain length), remove the nth node counted from the tail, detach it, and return the remaining readings.
Medium / Fixed pointer gap and sentinel / interactiveAlternate Relay Ends
Build a singly linked chain and relink it in first, last, second, next-to-last order, without changing any node’s reading. Return the new reading sequence; empty and single-node chains stay unchanged.
Medium / Find midpoint, reverse, weave / interactiveWhere this leads
Return to the roadmap to try a different kind of problem.