Topic 6 / 16
Linked List
MediumLinear~4 days
Moderate
progress0 / 15 solved
Pointer manipulation, slow/fast runners, and reversal patterns.
Prerequisites
Unlocks
Concept
Linked lists are chains of nodes connected by pointers. Unlike arrays, there's no random access — traversal is always O(n). Most problems are solved with pointer manipulation: the slow/fast runner technique, reversal in-place, and maintaining extra pointers to keep track of prev/next.
When to use this pattern
- ◆Detect a cycle in a linked list
- ◆Find the middle node
- ◆Reverse a list or sublist
- ◆Merge two sorted lists
- ◆Remove nth node from end
Common patterns
Slow / fast pointers
Detect cycles, find midpoints. Fast moves 2x speed of slow.
In-place reversal
Swap next pointers iteratively with prev, curr, next variables.
Dummy head
Add a sentinel node before head to simplify edge cases (empty list, removing head).
Merge
Compare heads of two lists, advance the smaller one.
Visual walkthrough
Linked List
Reverse a Linked List
linked list
1
curr
→
2
→
3
→
4
→
5
→ null
curr
prev
next
reversed
Initialize: prev=null, curr=head
We'll reverse by redirecting each node's next pointer to its predecessor.
step 1/16
Brute force → optimal thinking
Brute force
Store all nodes in an array; process from there → O(n) space.
Observation
Most operations only need O(1) extra space if we adjust pointers in place.
Optimization
Use 2-3 pointers (prev, curr, next) and update links in a single pass.
Final complexity
O(n) time, O(1) space for most in-place operations.
Quick Recall Check
Why is a dummy head node useful in linked list problems?
In Floyd's cycle detection, what does it mean when slow and fast pointers meet?
To remove the nth node from the end in one pass, what gap do you maintain between two pointers?
Am I ready to move on?
Check each question you can answer confidently before moving to the next topic.
Progress is saved on this device