Linked lists

What it is

Linked-list problems are about manipulating pointers rather than values: reversing, splicing, or reordering nodes by changing what each node's next points to, usually with the constraint that you reuse existing nodes instead of building a new list. The recurring tools are a small number of pointers moving through the list at different speeds or from different starting points — a slow/fast pair to find a midpoint or detect a cycle, two pointers offset by a fixed gap to find a position from the end, or a dummy head node to avoid special-casing the first element.

When it applies

• You need to reverse, reorder, or splice a list using its own nodes, with the interviewer explicitly ruling out "copy everything into an array first."
• You need a structural property of the list itself — its length, its midpoint, whether it cycles — without being told the length up front.
• The list carries an extra pointer beyond next (a random pointer) that must be reproduced correctly in a copy.
• Random access by index mattering more than sequential rewiring, or being told to copy into an array anyway, means plain array or hash-map techniques are simpler and the pointer-chasing tricks add nothing.

Tells in the problem

• "Return the new head," "modify in place," or "you may not allocate new list nodes" for a singly linked list.
• "n-th from the end" or "middle of the list" — a length you don't know up front, since the list isn't indexable.
• "Detect a cycle" or "does the list loop back on itself" with no ability to compare node values.
• A node class with a second pointer field besides next (random, child) that a deep copy has to preserve.
• Digits or values stored one per node, added or compared node by node instead of as a single number.

The classic mistake

Losing the rest of the list by overwriting a node's next pointer before the pointer that was about to be replaced has been saved somewhere else — reversal is the classic site of this bug, where advancing to the next node after rewiring current.next leaves you unable to continue because the original next node is gone. The general fix is to always capture the node you're about to lose (next_node = current.next) before you touch any pointer on current, and to reach for a dummy head node whenever the operation might change what the first node of the result is, so the head case doesn't need separate logic from every other case.

Questions to start with

• Reverse Linked List — the base pointer-rewiring drill: save-then-relink, one node at a time.
• Merge Two Sorted Lists — splicing two lists together with a dummy head, reusing nodes rather than copying values.
• Linked List Cycle — introduces the slow/fast runner pair to answer a question the list's shape alone can't tell you directly.
• Remove Nth Node from End of List — two pointers offset by a fixed gap, so a single pass finds a position measured from the end.
• Reorder List — combines finding the midpoint, reversing the second half, and merging two halves in one problem.
• Copy List with Random Pointer — the hardest rewiring problem: an extra pointer that must resolve to copied nodes, not originals.
• Merge K Sorted Lists — extends the two-list merge to many lists, where a heap of current candidates replaces repeated pairwise merging.