Linked Lists & Fast/Slow Pointers
Pointer surgery: reversal, cycle detection, and finding the middle in one pass. The problems that test careful bookkeeping.
A linked list trades indexing for cheap pointer rewiring. Each node knows its value and where the next node lives. There is no O(1) jump to index i; reaching a node means walking from the head.
Interview linked-list problems are not about fancy data structures. They test bookkeeping: update pointers in the right order, avoid losing the rest of the list, and use dummy nodes or fast/slow pointers to simplify edge cases.
The mental model
A singly linked list is just nodes connected by next references:
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = nextThe key operation is rewiring links, not moving values. For reversal, keep three names: prev, cur, and nxt. Save nxt before overwriting cur.next, or you lose the remainder of the list.
def reverse(head):
prev = None
cur = head
while cur:
nxt = cur.next
cur.next = prev
prev = cur
cur = nxt
return prevA dummy head is a fake node before the real head. It makes insertions and deletions at the front look the same as insertions and deletions in the middle. Fast/slow pointers solve a different class of problem: one pointer moves twice as fast as the other, so their relative motion reveals cycles or the middle.
Pattern recognition
Variations
Worked problems
Draw the nodes for these. Linked-list bugs are usually pointer-order bugs, not algorithm-choice bugs.
Reverse Linked List
Given the head of a singly linked list, reverse the list in place and return the new head.
Approach. Walk through the list while carrying the already-reversed prefix in prev. Before redirecting cur.next, save the original next node. After the loop, prev is the old tail and new head.
Show solution
def reverse_list(head):
prev = None
cur = head
while cur:
nxt = cur.next
cur.next = prev
prev = cur
cur = nxt
return prevComplexity. O(n) time, O(1) extra space. Every node’s next pointer is rewired once.
Linked List Cycle
Given the head of a linked list, decide whether following next pointers ever loops back to a node already seen.
Approach. Use Floyd’s cycle detection. slow moves one step; fast moves two. In an acyclic list, fast reaches the end. In a cyclic list, fast laps slow and they meet inside the loop.
Show solution
def has_cycle(head):
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
return True
return FalseComplexity. O(n) time, O(1) extra space. The two pointers traverse at most a linear number of links before meeting or reaching the end.
Reorder List
Rearrange a list from L0 → L1 → ... → Ln into L0 → Ln → L1 → Ln-1 → ... by changing links in place. The function does not need to return anything.
Approach. Find the middle with fast/slow pointers, reverse the second half, then weave nodes from the first and reversed second halves. Splitting the list before reversing prevents accidental cycles during the merge.
Show solution
def reorder_list(head):
if not head or not head.next:
return
slow = head
fast = head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
second = slow.next
slow.next = None
prev = None
cur = second
while cur:
nxt = cur.next
cur.next = prev
prev = cur
cur = nxt
second = prev
first = head
while second:
first_next = first.next
second_next = second.next
first.next = second
second.next = first_next
first = first_next
second = second_nextComplexity. O(n) time, O(1) extra space. The list is scanned to find the middle, the second half is reversed, and the halves are merged in place.
The classic pitfall
When a linked-list solution feels full of head-specific branches, try adding a dummy node. It often turns four edge cases into one normal pointer update.