Linked lists explained with pictures: pointer rewiring, dummy heads and fast and slow pointers, with step-by-step diagrams and practice problems.
2 min read
5-question quiz
3 practice problems
head
1
2
3
null
A linked list stores items in nodes, and each node points to the next one. Interviewers like them because the code is short but easy to get wrong: they're really a test of how carefully you handle pointers and edge cases.
A linked list is like a train: each car is coupled to the next one, and the only way to reach car 3 is to walk from the engine.
python
1class ListNode:
2 def __init__(self, val=0, next=None):
3 self.val = val
4 self.next = next
head is the first node, and the last node's next is None (null in JavaScript). An empty list is just head = None.
A singly linked list
head
1
2
3
null
Each node holds a value and a link to the next node. The last link is null.
Linked list vs array
Operation
Array
Singly linked list
Read the k-th item
O(1)
O(k): walk from the head
Insert or delete at the front
O(n)
O(1)
Insert or delete after a node you already have
O(n)
O(1)
Find a value
O(n)
O(n)
Linked lists win when you add or remove in the middle a lot and already hold a pointer to the spot. Arrays win for anything indexed. In interviews, the list is usually given to you, and the question is what you can do in O(1) extra space.
Technique: rewiring pointers
Most list problems come down to changing next pointers in the right order. The golden rule: save what you're about to lose. Before you change node.next, keep a reference to the old node.next if you still need it.
Draw three or four boxes with arrows and step through your code by hand. Interviewers expect you to, and it catches most bugs.
Watch out
Before you change node.next, save the old value in a variable. Overwrite it first and the rest of the list is gone for good.
Technique: the dummy head
When the head itself might change (deleting the first node, merging lists, building a new list), create a placeholder node that points at the head:
python
1dummy = ListNode(0, head)
↑a placeholder in front of the head
2# ... work with dummy.next as the real head ...
3return dummy.next
↑the real head, even if it changed
The dummy means "the node before the first node" always exists, so you don't need a special case for the front of the list.
A dummy head
dummyhead
d
1
2
3
null
The dummy sits before the real head, so even the first node has a node before it.
Technique: fast and slow pointers
Move one pointer two steps at a time and another one step at a time.
When fast reaches the end, slow is in the middle.
If the list has a cycle, fast eventually laps slow and they meet.
To find the k-th node from the end, move fast k steps ahead first, then move both one step at a time: when fast reaches the end, slow is k nodes behind it.
All of these use O(1) extra space, which is usually the point of the question.
Fast and slow pointers find the middle1 / 3
slowfast
1
2
3
4
5
null
Both start at the head.
Common mistakes
Losing the rest of the list by overwriting next before saving it.
Forgetting the empty list (head is None) or the one-node list.
Returning the old head after reversing, instead of the new one.
Off-by-one errors in "k-th from the end": test with k = 1 and k = length.
Nice work!
You've got the big idea. Try the quick quiz below, then put it to work on the practice problems.
Quick quiz
5 questions. Pick an answer to see the explanation.
0/5
1What's the cost of reading the 500th item of a singly linked list, starting from the head?
2Why do many linked list solutions start with a dummy node pointing at the head?
3A slow pointer moves 1 step and a fast pointer moves 2 steps at a time. Where is slow when fast reaches the end?
4While reversing a list, you're about to set node.next = prev. What must you do first?
5How much extra space does reversing a linked list in place use?
Practise what you learned
Solve them in your browser, in Python or JavaScript.