Foundations
Linked Lists
Pointers, not indices. Reversal, cycle detection, and two-pointer tricks cover most of what shows up.
What is a linked list?
A linked list stores elements in nodes. Each node holds a value and a pointer to the next node:
Unlike an array, nodes are not stored contiguously in memory - each can live anywhere on the heap. The only entry point is the head pointer. The last node's next is None. To reach the kth element, you walk k links from the head: there is no index arithmetic shortcut.
The trade-off: linked lists give O(1) insert/delete at a known pointer (no shifting needed), and pay for it with O(n) random access. Arrays are the inverse. Most real systems prefer arrays for their cache locality, but linked lists appear in a disproportionate share of interview problems.
Core operations
| Operation | Time | Notes |
|---|---|---|
| Access by index | O(n) | Traverse from head |
| Traversal | O(n) | One pass |
| Insert at head | O(1) | Rewire two pointers |
| Insert at tail | O(n) or O(1) | O(1) with a tail pointer |
| Delete at head | O(1) | head = head.next |
| Delete (given prev) | O(1) | prev.next = node.next |
| Search | O(n) | Scan from head |
| Reverse | O(n) | Three-pointer in-place |
Traversal is the atomic building block - every other operation starts here:
Deletion requires a reference to the preceding node so you can redirect its next. Deleting the head is a special case - there is no predecessor, so you just reassign head = head.next.
Key patterns
Reversal
Flip every node's next pointer so the list runs the other way - one pass, no extra memory.
When to use - the task is "reverse this list" or a slice of it, or the problem is easier read back-to-front (for example, checking a list against its reverse). Do it in place: that buys O(1) space, where copying into a new list or stack would cost O(n).
How it works - hold three pointers: prev, curr, next_node. Each step does three things - stash next_node = curr.next, point curr.next = prev, then move prev and curr forward one. The stash is mandatory: the moment you overwrite curr.next, that saved pointer is your only handle on the rest of the list. One pass, O(n) time, O(1) space; when curr runs off the end, prev is the new head.
Example: reverse 1-2-3-4-5 in place. prev starts at None and curr on node 1. Each pass points the current node back at prev - node 1 lands on None, then 2 points to 1, 3 to 2, and so on - then advances both pointers, so after five passes prev sits on node 5, the new head, and the list reads 5-4-3-2-1. The visualizer below flips one arrow per pass.
next_node = curr.next must come before curr.next = prev. Reversing that order overwrites the only pointer to the rest of the list.Fast/slow pointers
Two pointers move at different speeds - fast takes two steps for every one slow takes.
When to use - you need the middle node, or you need to know whether the list has a cycle, in one pass with O(1) space. The naive alternatives are worse: copy the list into an array (O(n) space), or walk it twice to count the length first.
How it works - each iteration, advance fast by two and slow by one. When fast reaches the tail it has traveled twice as far, so slow is at the midpoint. For cycle detection, a loop lets the faster pointer lap the slower one until they land on the same node; with no cycle, fast just falls off the end. Since fast jumps two at a time, check both fast and fast.next before you dereference.
Example: find the middle / detect a cycle. On 4, 7, 9, 11, 7 with the last node looping back to the first 7, both pointers start on the head 4, and because fast gains one node per iteration it laps slow on the fourth - both land on the tail node and the run returns True. On the acyclic preset 1, 2, 3, fast instead runs past the tail and the answer is False. The visualizer below plays out both endings.
while fast and fast.next not just while fast. On an even-length list fast.next.next dereferences None and crashes without the second check.Two-pointer with offset
Put a fixed gap of n nodes between two pointers, then move them together so the gap never changes.
When to use - the problem is phrased relative to the end of a singly linked list ("the nth node from the end", "delete the nth-from-last"). You can't walk backward, and you'd rather not make the two passes that counting the length first would take.
How it works - advance fast n steps on its own, then move fast and slow together until fast reaches the last node. The constant n-node gap leaves slow on the predecessor of the nth-from-end - the exact node whose next you rewrite to delete. Put a dummy node before the head and the case where the target is the head itself stops being special. One pass, O(1) space.
Example: delete the 2nd node from the end of 1-2-3-4-5. Both pointers start on a dummy parked before the head, and fast takes a 2-step head start to node 2 - that fixed gap is what lines up the end of the walk. Both then advance in lockstep until fast reaches node 5, the last node, leaving slow on node 3, one before the target, and slow.next is rewired to skip node 4. The visualizer below walks the pair node by node.
fast is the last node leaves slow on the target's predecessor (what deletion needs). If you instead stop when fast becomes None, slow lands on the target itself. Trace a 3-node list with n=1 before committing.When to reach for a linked list
- The problem gives you nodes and asks you to rearrange pointers (reverse, merge, split, reorder).
- You need an LRU cache - doubly linked list + hash map is the canonical O(1) solution.
- The problem mentions a cycle - fast/slow pointers are the go-to.
- You need to find the nth from the end - two-pointer with an n-step head start.
- The problem involves merging two sorted lists - dummy head + two-pointer merge.
- The problem involves potential head deletion (remove all nodes with value X) - dummy head.
Done reading? Mark it so it sticks in your dashboard.