Nodes and pointers
Think of a treasure hunt: each clue tells you where the next clue is. To find the fifth clue, you must follow the first four. A linked list works the same way:
- each node holds a value and a reference to the next node,
- the list is just a reference to the first node, the head,
- the last node’s
nextis empty (nil/null).
Unlike an array, you can’t jump to position 5 directly (that’s O(n)), but you can insert or remove a node anywhere in O(1) if you already have the node before it: just change one next.
A singly linked list trades O(1) indexed access for O(1) insertion and removal at a known node, at the cost of poor memory locality and one pointer per element. In interviews the data structure is a vehicle for pointer manipulation under invariants: maintain prev/current/next correctly, use sentinels to remove head special cases, and use two pointers moving at different speeds to find middles, k-th from end, and cycles in O(1) extra space. The Detailed version adds the math behind cycle detection and production details like recursion depth and ARC deallocation of long chains.
final class ListNode {
var value: Int
var next: ListNode?
init(_ value: Int, _ next: ListNode? = nil) { self.value = value; self.next = next }
}
func printList(_ head: ListNode?) {
var node = head
while let current = node {
print(current.value, terminator: " ")
node = current.next
}
}
let head = ListNode(1, ListNode(2, ListNode(3))) // 1 → 2 → 3
printList(head) // 1 2 3class ListNode(var value: Int, var next: ListNode? = null)
fun printList(head: ListNode?) {
var node = head
while (node != null) {
print("${node.value} ")
node = node.next
}
}
val head = ListNode(1, ListNode(2, ListNode(3))) // 1 → 2 → 3
printList(head) // 1 2 3class ListNode {
int value;
ListNode next;
ListNode(int value, ListNode next) { this.value = value; this.next = next; }
ListNode(int value) { this(value, null); }
}
static void printList(ListNode head) {
for (ListNode node = head; node != null; node = node.next) {
System.out.print(node.value + " ");
}
}
ListNode head = new ListNode(1, new ListNode(2, new ListNode(3))); // 1 → 2 → 3
printList(head); // 1 2 3class ListNode {
constructor(public value: number, public next: ListNode | null = null) {}
}
function printList(head: ListNode | null) {
const values: number[] = [];
for (let node = head; node !== null; node = node.next) values.push(node.value);
console.log(values.join(" "));
}
const head = new ListNode(1, new ListNode(2, new ListNode(3))); // 1 → 2 → 3
printList(head); // 1 2 3Reversing a list in place
The classic first question: turn 1 → 2 → 3 → 4 → 5 into 5 → 4 → 3 → 2 → 1 without a second list. Walk the list once with three references: prev (the part already reversed), current, and next, saved before you change current.next:
func reverseList(_ head: ListNode?) -> ListNode? {
var prev: ListNode? = nil
var current = head
while let node = current {
let next = node.next // 1. save the rest of the list
node.next = prev // 2. turn this node around
prev = node // 3. the reversed part now starts here
current = next // 4. continue with the saved rest
}
return prev
}fun reverseList(head: ListNode?): ListNode? {
var prev: ListNode? = null
var current = head
while (current != null) {
val next = current.next // 1. save the rest of the list
current.next = prev // 2. turn this node around
prev = current // 3. the reversed part now starts here
current = next // 4. continue with the saved rest
}
return prev
}ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode current = head;
while (current != null) {
ListNode next = current.next; // 1. save the rest of the list
current.next = prev; // 2. turn this node around
prev = current; // 3. the reversed part now starts here
current = next; // 4. continue with the saved rest
}
return prev;
}function reverseList(head: ListNode | null): ListNode | null {
let prev: ListNode | null = null;
let current = head;
while (current !== null) {
const next = current.next; // 1. save the rest of the list
current.next = prev; // 2. turn this node around
prev = current; // 3. the reversed part now starts here
current = next; // 4. continue with the saved rest
}
return prev;
}O(n) time, O(1) space.
Losing the rest of the list
The order of those four lines is the whole problem. Here’s a version with one step in the wrong place:
Tap the line with the bug.
func reverseList(_ head: ListNode?) -> ListNode? {
var prev: ListNode? = nil
var current = head
while let node = current {
node.next = prev
prev = node
current = node.next
}
return prev
}fun reverseList(head: ListNode?): ListNode? {
var prev: ListNode? = null
var current = head
while (current != null) {
current.next = prev
prev = current
current = current.next
}
return prev
}ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode current = head;
while (current != null) {
current.next = prev;
prev = current;
current = current.next;
}
return prev;
}function reverseList(head: ListNode | null): ListNode | null {
let prev: ListNode | null = null;
let current = head;
while (current !== null) {
current.next = prev;
prev = current;
current = current.next;
}
return prev;
}Hint: Trace 1 → 2 → 3. After line 5 runs for node 1, what is node 1's next?
Line 5 overwrites next with prev (empty on the first step), and line 7 then reads next to move on, but it’s no longer the rest of the list: it’s the empty prev. The loop stops after the first node, and the function returns 1 alone. Nodes 2 and 3 are lost: nothing points to them anymore.
Save the next node before changing the pointer, exactly as in the code above: let next = node.next first, then rewire, then move to the saved next. When in doubt in linked-list code, draw the boxes and arrows for three nodes and update them line by line.
- Read before you overwrite: save
next, rewire, advance. Iterative reversal is O(n) time and O(1) space; the recursive one uses O(n) stack and overflows on long lists.
var prev: ListNode? = nil, current = head
while let node = current { let next = node.next; node.next = prev; prev = node; current = next }var prev: ListNode? = null; var current = head
while (current != null) { val next = current.next; current.next = prev; prev = current; current = next }ListNode prev = null, current = head;
while (current != null) { ListNode next = current.next; current.next = prev; prev = current; current = next; }let prev: ListNode | null = null, current = head;
while (current !== null) { const next: ListNode | null = current.next; current.next = prev; prev = current; current = next; }Check this part
What is the cost of reaching the 1,000th node of a linked list?
When reversing a list, what must you do before setting current.next = prev?
A recursive reverse works in tests. What happens on a 100,000-node list?