Linked List
A linked list is a chain of nodes, each holding data and a pointer to the next node. Unlike an array, it doesn't allow O
- access by index, but inserting or deleting at a known position costs only O
- because only a few pointers need to be relinked
The classic problems revolve around pointer manipulation: reversing, merging, finding the middle, or detecting a cycle with a fast and a slow pointer. A common bug is breaking the chain by forgetting to save the next pointer before changing a link.
Like a train of connected cars — each car (node) holds cargo (val) and a coupling to the next car (next).
- To reach the last car you have to walk through every car; you can't jump straight to an index like in an array.
- In exchange, attaching or detaching a car in the middle is just changing a couple of couplings, O(1).
How to spot it
When you see these cues in the problem, reach for Linked List
| Keyword in the problem | Why it points to this topic |
|---|---|
| given a list head | Work with next pointers, not array indices |
| reverse / merge / split | Save next before relinking to avoid losing the chain |
| fast & slow pointers | Find middle or detect a cycle |
When to use
4 typical situations where this topic applies
Lots of inserts/deletes at the head, with no need for index access
Reversing, merging, or splitting a chain of nodes
Detecting a cycle with 2 pointers, fast & slow
The data size is unknown in advance and you don't want to copy on growth like an array does
When NOT to use
3 situations where this topic doesn't fit — know them so you don't overuse them
You need random access by index: a Linked List is O(n) per access — an Array is far better
You need Binary Search on the data: a Linked List has no random access, so it doesn't fit
Cache locality matters for performance: an Array has a clear advantage in the CPU cache
Illustration
A diagram of how this topic works.
Each node holds a value plus a pointer to the next node. No random access — to reach the k-th element you walk from the head.
Code template
Most problems in this topic share this scaffold — copy it, then fill in the problem-specific logic.
function listPattern(head: ListNode | null): ListNode | null {
const dummy = new ListNode(0) // dummy node smooths head edge cases
dummy.next = head
let prev: ListNode | null = dummy
let curr = head
while (curr) {
const nextNode = curr.next // save next BEFORE relinking
// ... relink pointers: curr.next = ..., prev.next = ...
prev = curr
curr = nextNode
}
return dummy.next
}Recap
A quick summary — reread it before your interview
Key points
Accessing the i-th node takes O(n); insert/delete once you hold a pointer to the spot is O(1)
Use a dummy head node to handle the start of the list cleanly
The 2-pointer technique: fast moves 2 steps, slow moves 1 — find the middle / detect a cycle
Common mistakes
Losing the reference to the rest of the list while reversing — save next before reassigning
Forgetting the empty list (head = null) or single-node cases
Accessing node.next when node is already null → runtime error
Complexity
Duyệt O(n), thêm/xoá tại con trỏ O(1), bộ nhớ phụ O(1)Practice problems for this topic
Grouped by difficulty — work through them in order to build confidence