Coding Interview: Patterns & DSA · Linked Lists, Stacks & Queues · Lesson 1 of 2
Linked lists & fast/slow pointers
A linked list is nodes each pointing to the next. You cannot index into it — you must walk it — so the key patterns are pointer manipulation: fast/slow (Floyd's) pointers and in-place reversal.
Fast/slow pointers
Move one pointer one step and another two steps per iteration. When fast reaches the end, slow is at the middle. If the list has a cycle, fast eventually laps and meets slow — that is Floyd's cycle detection, in O(1) space.
def has_cycle(head): slow = fast = head while fast and fast.next: slow = slow.next # +1 fast = fast.next.next # +2 if slow is fast: return True # they met -> cycle return False
In-place reversal
def reverse(head): prev, cur = None, head while cur: nxt = cur.next # save next cur.next = prev # flip the pointer prev = cur # advance prev cur = nxt # advance cur return prev # new head
Save next before you flipWhen reversing, the moment you set
cur.next = prev you lose the rest of the list unless you saved nxt first. Draw the three pointers before you code — this is where most people crash.Recognize itFast/slow solves find the middle, detect a cycle, find the cycle start, and nth-from-end (offset the fast pointer by n). Reversal underlies palindrome and reorder problems.
◆ Lock it in
- Fast/slow pointers find the middle and detect cycles in
O(1)space. - In-place reversal flips
cur.nexttoprev— save next first. - Offsetting fast by
nfinds the nth node from the end in one pass.
Feynman drill — say it out loudExplain why a fast pointer moving twice as quickly is guaranteed to meet a slow pointer inside a cycle.
Step 1 rate your confidence · Step 2 pick your answer
With fast/slow pointers, when the fast pointer reaches the end of the list, the slow pointer is at:
Step 1 — how sure are you?