Linked List Pointer Techniques
Three techniques solve most linked list problems in O(1) extra space: fast and slow pointers, reversing links in place, and a dummy head node.
Most linked list problems come down to three techniques for moving along the list and rewiring it in place: two pointers moving at different speeds, reversing the direction of links, and a dummy node placed before the head.
The idea
A linked list is a chain of nodes. Each node holds a value and a reference, next, to the node after it. The last node's next is null.
head → [1] → [2] → [3] → [4] → nullTwo facts shape every solution:
- There are no indexes. The only way to reach the fourth node is to walk through the first three. You cannot jump to the middle or step backwards.
- Changing the list means changing
nextreferences. Nothing is shifted along, as it would be in an array, so an insertion or removal is O(1) once you are standing in the right place.
Copying the values into an array makes most problems trivial, but costs O(n) extra space. The techniques below do the same work with a few variables.
In the examples a node is any object with value and next properties.
When to use each technique
| The problem asks for | Technique |
|---|---|
| The middle node, or the k-th from the end | Fast and slow pointers |
| Whether the list loops back on itself, and where | Fast and slow pointers |
| Reversing a list, or part of one | Link reversal |
| Checking for a palindrome in O(1) space | Find the middle, reverse the second half |
| Removing nodes, merging lists, building a new list | Dummy head |
Technique 1: fast and slow pointers
Start two pointers at the head. Move one a single step at a time and the other two steps. When the fast one reaches the end, the slow one has covered half the distance, so it is at the middle.
// The middle node. With an even number of nodes, the second of the two middles.
function middleNode(head) {
let slow = head;
let fast = head;
while (fast !== null && fast.next !== null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}The same pair of pointers detects a cycle: a list whose last node points back to an earlier one instead of to null. Walking such a list never ends. But if the fast pointer is going round a loop, it must eventually come up behind the slow pointer and land on it, like a faster runner lapping a slower one on a track.
function hasCycle(head) {
let slow = head;
let fast = head;
while (fast !== null && fast.next !== null) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) return true;
}
return false;
}The fast pointer cannot jump over the slow one. Inside the loop, the gap between them shrinks by exactly one node per step, so it reaches zero.
The loop condition checks both fast and fast.next because the fast pointer takes two steps. Checking only one of them lets the second step read next of null.
Technique 2: reversing links
To reverse a list, walk along it and turn each next reference round to point at the node before. Three variables are needed: the node being processed, the one before it, and a saved reference to the one after, because overwriting current.next would otherwise lose the rest of the list.
before: null [1] → [2] → [3] → null
↑
current
after: null ← [1] ← [2] ← [3]
↑
new headThe four steps, repeated for each node, are: save next, point current.next backwards, move previous forward, move current forward. Reverse Linked List works through it line by line.
Reversal is rarely the whole problem. It is a building block: reverse the second half to compare it with the first, reverse a stretch between two positions, or reverse the list in groups.
Technique 3: the dummy head
Removing a node means changing the next of the node before it. The head has no node before it, so code that removes or inserts nodes ends up with a special case for the head.
A dummy node placed in front of the head removes that case. Every real node now has a predecessor. At the end, the real head is whatever follows the dummy.
// Remove every node holding `value`.
function removeValue(head, value) {
const dummy = { value: null, next: head };
let previous = dummy;
while (previous.next !== null) {
if (previous.next.value === value) {
previous.next = previous.next.next; // unlink the node
} else {
previous = previous.next;
}
}
return dummy.next;
}Note that previous stays where it is after an unlink. The node that slid into previous.next has not been checked yet.
Return dummy.next, not head. If the original head was removed, head still refers to a node that is no longer in the list.
Complexity
Each technique walks the list a fixed number of times.
- Time: O(n).
- Space: O(1). Only a few pointers are stored, however long the list is. That is the whole reason to prefer these techniques over copying the list into an array.
Common mistakes
- Losing the rest of the list. Overwriting
node.nextbefore saving the old value cuts off everything after it. Save first. - Reading
nextofnull. Before writingnode.next.next, be sure bothnodeandnode.nextexist. - Returning the old head. After a reversal or a removal the head may have changed. Return the new one.
- Comparing values instead of nodes when detecting a cycle. Two different nodes can hold the same value. Compare the nodes themselves with
===. - Creating a cycle by accident. After reversing part of a list, the old first node of that part still points forwards unless it is reconnected. Draw the pointers on paper for a three-node list and check every
next. - Forgetting the empty list and the one-node list. Both are valid inputs, and both are where
nullerrors show up.
Practice problems
| Problem | Difficulty | Time | Space | Read |
|---|---|---|---|---|
| Reverse Linked List | easy | O(n) | O(1) | Medium read: 6 min |
| Linked List Cycle II | medium | O(n) | O(1) | Medium read: 7 min |
| Reverse Nodes in k-Group | hard | O(n) | O(1) | Medium read: 8 min |