Linked Lists¶
Linked lists are the first data structure that forces you to think about pointers — not just values. The reason engineers struggle with linked list problems is not the logic; it’s the spatial reasoning. Before you write a single line of code, you need to be able to draw the state of the list before and after each operation. If you skip drawing, you will lose references, corrupt the list, and wonder why your code produces garbage. This file teaches the structure, then drills the spatial reasoning.
1. Singly Linked List¶
Each node holds a value and a pointer to the next node. The list is accessed only through the head pointer.
Node structure:
┌───────┬──────┐ ┌───────┬──────┐ ┌───────┬──────┐
│ val │ next │────▶│ val │ next │────▶│ val │ null │
│ 1 │ │ │ 2 │ │ │ 3 │ │
└───────┴──────┘ └───────┴──────┘ └───────┴──────┘
▲
head
Traversal — O(n): Follow next pointers from head until null. No random access — to reach node at index k, you must traverse k nodes.
Insert at head — O(1):
new_node.next = head
head = new_node
Insert at tail — O(n): Must traverse to find the last node, then set last.next = new_node. (O(1) if you maintain a tail pointer separately.)
Insert at position k — O(k): Traverse to node k-1, then:
// BEFORE: ... → [k-1] → [k] → [k+1] → ...
// AFTER: ... → [k-1] → [new] → [k] → [k+1] → ...
new_node.next = prev.next
prev.next = new_node
Delete node at position k — O(k): Traverse to node k-1, then:
prev.next = prev.next.next // skips node k; it gets garbage collected
Critical: if you do curr = curr.next first and then try to reconnect, you’ve already lost the reference to curr.next.next. Always set the new link before breaking the old one.
2. Doubly Linked List¶
Each node has both next and prev pointers.
null ←──┬───────┬──────┐ ┌──────┬───────┬──────┐ ┌──────┬───────┬──── null
│ val │ next │────▶│ prev │ val │ next │────▶│ prev │ val │
│ 1 │ │ │ │ 2 │ │ │ │ 3 │
└───────┴──────┘ └──────┴───────┴──────┘ └──────┴───────┘
▲ ▲
head tail
Key advantage over singly linked: O(1) deletion given a node reference.
In a singly linked list, to delete node X, you need the node before X — so you must traverse to find it (O(n)). In a doubly linked list, X.prev gives you the predecessor directly:
X.prev.next = X.next
if X.next != null:
X.next.prev = X.prev
This is why LRU cache implementations use doubly linked lists — you need O(1) removal from any position.
Memory cost: 2 pointers per node instead of 1. For small values, this overhead is significant (doubles the pointer overhead).
3. Circular Linked List¶
The last node’s next points back to head (or to some other node). No null terminator.
head
▼
┌─────┴─────┐ ┌───────────┐ ┌───────────┐
│ 1 │────▶│ 2 │────▶│ 3 │
└───────────┘ └───────────┘ └─────┬─────┘
▲ │
└───────────────────────────────────┘
Use case: Round-robin schedulers. OS process scheduling uses a circular list of runnable processes — advance to the next process, wrap around when you hit the “end.”
Traversal danger: Naively following next pointers will loop forever. Always track either the starting node or a count.
4. Pointer Manipulation Mental Model¶
Rule: draw before you code. Every. Single. Time.
The three-step pointer surgery protocol:
Draw the list before the operation with labeled nodes and arrows
Draw the list after the operation showing what you want
Identify the minimum pointer changes needed to go from state 1 to state 2, and the order that doesn’t lose any reference
Example — reverse a singly linked list iteratively:
Before: null ← [1] → [2] → [3] → [4] → null
After: null ← [4] → [3] → [2] → [1] → null
You need three pointers: prev, curr, next_temp.
prev = null
curr = head
while curr != null:
next_temp = curr.next // save next before overwriting
curr.next = prev // reverse the pointer
prev = curr // advance prev
curr = next_temp // advance curr
return prev // prev is the new head
The next_temp save is non-negotiable. If you do curr.next = prev first without saving curr.next, you’ve permanently lost the rest of the list.
5. Classic Problems with Full Derivations¶
5.1 Reverse a Linked List (Iterative)¶
Already shown above. Time: O(n), Space: O(1).
5.2 Reverse a Linked List (Recursive)¶
reverse(head):
if head == null or head.next == null:
return head
new_head = reverse(head.next) // reverse the rest
head.next.next = head // make the next node point back to us
head.next = null // cut the forward pointer
return new_head
Time: O(n), Space: O(n) — call stack depth is n. This is worse than iterative on space. Know both; prefer iterative.
5.3 Detect Cycle — Floyd’s Algorithm¶
Problem: Does the linked list contain a cycle?
Brute force: Track visited node addresses in a hash set. O(n) time, O(n) space.
Floyd’s (slow/fast pointers): O(n) time, O(1) space.
slow = head
fast = head
while fast != null and fast.next != null:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True // cycle detected
return False
Why does this work? If there’s no cycle, fast reaches null and we return False. If there’s a cycle of length L, both pointers eventually enter the cycle. At that point, fast gains 1 step on slow per iteration. The distance between them decreases by 1 each iteration. Since the cycle has length L, they must meet within L iterations of both being in the cycle. The total iterations is at most O(n).
The key invariant: once inside the cycle, the relative distance between slow and fast decreases by exactly 1 per step. Zero distance means they’ve met.
Extension — find the cycle start: After detecting the cycle (slow == fast), reset slow to head and advance both slow and fast one step at a time. They meet at the cycle entry point. The proof involves a modular arithmetic argument — if you’re curious, work through it (LeetCode #142).
5.4 Find Middle Node¶
slow = head
fast = head
while fast != null and fast.next != null:
slow = slow.next
fast = fast.next.next
return slow // slow is at the middle
When fast reaches the end (for even-length lists: fast.next == null; for odd: fast == null), slow is at the middle. For even-length lists, slow lands on the second middle node — if you need the first, check fast.next.next == null before advancing.
5.5 Merge Two Sorted Lists¶
merge(l1, l2):
dummy = Node(-1) // sentinel head to avoid special-casing head update
curr = dummy
while l1 != null and l2 != null:
if l1.val <= l2.val:
curr.next = l1
l1 = l1.next
else:
curr.next = l2
l2 = l2.next
curr = curr.next
curr.next = l1 if l1 != null else l2 // attach remaining
return dummy.next
The dummy/sentinel node pattern avoids special-casing the head pointer assignment. Always use a dummy node when building a new list by appending — it saves 3–4 lines of edge case handling and is universally understood.
6. Practice Problems¶
Easy¶
LeetCode #206 — Reverse Linked List (iterative + recursive, both)
LeetCode #21 — Merge Two Sorted Lists (sentinel node pattern)
Medium¶
LeetCode #141 — Linked List Cycle (Floyd’s, O(1) space)
LeetCode #142 — Linked List Cycle II (Floyd’s extension, find cycle start)
LeetCode #19 — Remove Nth Node From End (two-pointer with n-gap)
Hard¶
LeetCode #25 — Reverse Nodes in k-Group (pointer surgery in groups; requires drawing first)
What Most Engineers Get Wrong¶
Losing the reference. The #1 bug in linked list problems is modifying a pointer before saving what it was pointing to. curr.next = prev destroys your ability to continue traversal if you haven’t already saved curr.next. The habit is: save the pointer you’re about to overwrite, every time, before overwriting it.
Not using a dummy/sentinel node. Head-of-list operations are almost always special cases — inserting before head, deleting head, starting a new list. A dummy node (allocate a node with a throwaway value, return dummy.next at the end) eliminates all head special cases. Use it reflexively.
Recursive reversal space: Many people prefer the recursive version because it “looks elegant.” In an interview context, the recursive reverse is O(n) space due to the call stack. The iterative version is O(1). Know both but understand the trade-off and state it unprompted.
Return to README.md · Next: 03_stacks_and_queues.md