Linked lists

Why it matters

Linked-list problems are short to state and unforgiving to code: one misordered assignment drops the rest of the list or creates a cycle. They test whether you can keep an invariant while mutating structure, the same skill you need for trees, graphs and concurrent data structures. Real systems use linked lists inside other structures: an LRU cache is a hash map plus a doubly linked list, and allocators, schedulers and kernels keep free lists and run queues.

Core ideas

Pattern: Linked-list pointer manipulation. Before you overwrite a pointer, save whatever it was keeping reachable. Iterative reversal holds three references with the invariant "prev heads the already-reversed prefix and curr heads the untouched suffix":

prev, curr = None, head
while curr:
    nxt = curr.next      # save the rest of the list
    curr.next = prev     # reverse one link
    prev, curr = curr, nxt
return prev

Each node is visited once: O(n) time, O(1) space. The recursive version is shorter but uses O(n) stack, which can overflow on long lists.

Dummy heads. Allocate a sentinel node whose next is the real head. Inserting before the head, deleting the head and building a merged list then need no special case; return dummy.next. Merge Two Sorted Lists and Remove Nth Node From End are both simpler with one.

Pattern: Fast and slow pointers. Advance slow by one and fast by two.

• Middle: when fast runs off the end, slow is at the middle. Which middle you get for even lengths depends on the loop condition, so test lengths 1 to 4.
• Cycle detection (Floyd): inside a cycle fast gains one node per step on slow, so they meet before slow completes a lap; without a cycle fast reaches null.
• Cycle entry: let a be the distance from the head to the entry, b the distance from the entry to the meeting point and c the cycle length. Fast has walked twice as far as slow, so a + b is a multiple of c. Restart one pointer at the head and move both one step at a time: after a steps both stand on the entry.
• The same reasoning applies to any sequence x, f(x), f(f(x)), ... such as Happy Number or Find the Duplicate Number.

Gap pointers. For the n-th node from the end in one pass, move a lead pointer n steps ahead, then advance both until the lead reaches the end.

Composition. Many medium problems chain primitives. Reorder List is find the middle, reverse the second half, interleave. Palindrome Linked List is find the middle, reverse, compare, and ideally restore the list afterwards.

Lists with maps. A doubly linked list removes a known node and inserts at either end in O(1); a hash map from key to node supplies O(1) access. Together they make an LRU cache with O(1) get and put: move a node to the front on access, evict from the back.

Arrays versus lists. Lists win only when you already hold a reference to the splice point. Arrays win on indexing, memory overhead and cache locality; for small and medium sizes, shifting contiguous memory is often faster in practice than chasing pointers.

Common misconceptions

• "Inserting into a linked list is O(1)." Only once you hold a reference to the neighbor; finding the position is O(n).
• "Recursive list code is O(1) space." Each call adds a stack frame, so recursion over n nodes uses O(n) space.
• "Fast and slow pointers meet at the cycle entry." They meet somewhere inside the cycle; the entry needs the second phase from the head.
• "Edge cases are rare." Empty lists, single nodes, two nodes and changes at the head or tail are where bugs cluster; a dummy head removes many of them.
• "Linked lists beat arrays for insert-heavy code." Pointer chasing causes cache misses; measure before assuming the list wins.

How to approach it

Draw three or four nodes and every pointer change before coding, and say each invariant aloud. Use a dummy head whenever the head might change. Test the empty list, one node and two nodes explicitly. Interviewers watch for lost references and ask why Floyd's second phase finds the entry; at mid and senior levels expect to design the LRU structure and discuss what changes when several threads use it.