Linked Lists
Topic 3 of 7, with 3 concept checks. Pointer manipulation, fast/slow pointers, and reversal
Rewire links without losing the remaining chain
Pointer rewiring
Name the nodes that must survive each pointer change, save the untouched suffix first, and use sentinels when they remove special handling at a linked-list boundary.
Core lesson 01
Use two pointers, one moving one step at a time (slow) and one moving two steps (fast); if there's a cycle, they're guaranteed to eventually meet inside it.
In a cyclic list, the fast pointer gains one extra step on the slow pointer every iteration, so the gap between them (measured around the cycle) shrinks by one each time - guaranteeing they meet within one full loop of the cycle. This achieves O(1) space, versus the O(n) space a hash-set-of-visited-nodes approach would need.
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
return True
return FalseWhat to remember
How do you detect a cycle in a linked list without extra space?
Common footguns
- Checking fast.next.next without first checking fast.next is not None - raises an AttributeError near the end of the list.
Core lesson 02
Walk the list once, keeping a prev pointer (starting at None); for each node, save its next node before reversing its pointer to prev, then advance both forward.
Reversal is a pointer-rewiring exercise: at each node you want current.next to point backward to prev instead of forward. The trap is that overwriting current.next destroys your only way to reach the rest of the original list - so you must capture next_node = current.next FIRST, before reassigning current.next = prev.
def reverse_list(head):
prev = None
current = head
while current:
next_node = current.next # save before overwriting
current.next = prev
prev = current
current = next_node
return prev # new headWhat to remember
What's the cleanest way to reverse a linked list?
Common footguns
- Overwriting current.next before saving it - permanently loses the rest of the original list.
Before: 1 -> 2 -> 3 -> None Step 1: None <- 1 2 -> 3 -> None (prev=1, current=2) Step 2: None <- 1 <- 2 3 -> None (prev=2, current=3) Step 3: None <- 1 <- 2 <- 3 (prev=3, current=None -- done)
Core lesson 03
Move slow one step and fast two steps per iteration; when fast reaches the end, slow has traveled exactly half the distance, landing on the middle node.
Since fast moves twice as fast as slow, by the time fast has traversed the whole list, slow has covered exactly half of it. This avoids a first pass to count length and a second pass to walk to the midpoint - the same fast/slow mechanism that detects cycles also finds midpoints, just with a different stopping condition.
def middle_node(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow # middle node (second middle if even length)What to remember
How do you find the middle of a linked list in one pass?
Common footguns
- Off-by-one confusion about which node counts as 'the middle' for even-length lists - clarify with the problem statement whether it wants the first or second middle.
Python lab
Browser Python lab
Runtime · idle
Python loads on your first run. Your code stays in this browser.
Best practices
- Use fast/slow pointers for cycle detection, finding the middle, or finding the nth-from-end node.
- Draw the pointers out on paper/whiteboard before coding - linked list bugs are almost always about operation order.
- Use a dummy/sentinel head node to simplify edge cases when the head itself might change.
- Always save the 'next' reference before overwriting any node's pointer.
Apply the concept in Interview practice
Reverse Linked ListeasyLeetCode #206 · O(n) time, O(1) space
The prev/current/next-node walk shown above.
Open problemLinked List CycleeasyLeetCode #141 · O(n) time, O(1) space
Floyd's tortoise and hare, as above.
Open problemMerge Two Sorted ListseasyLeetCode #21 · O(n+m) time
Use a dummy head and a tail pointer; repeatedly attach whichever list's current node is smaller, advancing that list.
Open problemRemove Nth Node From End of ListmediumLeetCode #19 · O(n) time, one pass
Use two pointers with a gap of n between them; when the front pointer reaches the end, the back pointer is right before the node to remove.
Open problemAdd Two NumbersmediumLeetCode #2 · O(max(n,m)) time
Walk both lists simultaneously like manual addition, tracking a carry digit, building a new result list node by node.
Open problemConcept checks
How do you detect a cycle in a linked list without extra space?
Hint
Two pointers moving at different speeds will eventually meet if there's a loop.
This is Floyd's cycle detection, also called the tortoise and hare.
Answer
Use two pointers, one moving one step at a time (slow) and one moving two steps (fast); if there's a cycle, they're guaranteed to eventually meet inside it.
In a cyclic list, the fast pointer gains one extra step on the slow pointer every iteration, so the gap between them (measured around the cycle) shrinks by one each time - guaranteeing they meet within one full loop of the cycle. This achieves O(1) space, versus the O(n) space a hash-set-of-visited-nodes approach would need.
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
return True
return FalseWatch out
- Checking fast.next.next without first checking fast.next is not None - raises an AttributeError near the end of the list.
What's the cleanest way to reverse a linked list?
Hint
Track three pointers as you walk: previous, current, and next.
You must save 'next' before overwriting current's pointer, or you lose the rest of the list.
Answer
Walk the list once, keeping a prev pointer (starting at None); for each node, save its next node before reversing its pointer to prev, then advance both forward.
Reversal is a pointer-rewiring exercise: at each node you want current.next to point backward to prev instead of forward. The trap is that overwriting current.next destroys your only way to reach the rest of the original list - so you must capture next_node = current.next FIRST, before reassigning current.next = prev.
def reverse_list(head):
prev = None
current = head
while current:
next_node = current.next # save before overwriting
current.next = prev
prev = current
current = next_node
return prev # new headBefore: 1 -> 2 -> 3 -> None Step 1: None <- 1 2 -> 3 -> None (prev=1, current=2) Step 2: None <- 1 <- 2 3 -> None (prev=2, current=3) Step 3: None <- 1 <- 2 <- 3 (prev=3, current=None -- done)
Watch out
- Overwriting current.next before saving it - permanently loses the rest of the original list.
How do you find the middle of a linked list in one pass?
Hint
The same fast/slow pointer idea from cycle detection, applied differently.
When fast reaches the end, slow is exactly at the middle.
Answer
Move slow one step and fast two steps per iteration; when fast reaches the end, slow has traveled exactly half the distance, landing on the middle node.
Since fast moves twice as fast as slow, by the time fast has traversed the whole list, slow has covered exactly half of it. This avoids a first pass to count length and a second pass to walk to the midpoint - the same fast/slow mechanism that detects cycles also finds midpoints, just with a different stopping condition.
def middle_node(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow # middle node (second middle if even length)Watch out
- Off-by-one confusion about which node counts as 'the middle' for even-length lists - clarify with the problem statement whether it wants the first or second middle.