1Understand
The idea
Move one pointer twice as fast as the other. When the fast one reaches the end, the slow one is at the middle; if the list has a cycle, the fast one eventually laps the slow one and they meet. Starting one pointer k steps ahead finds the k-th node from the end in a single pass.
Intuition
Move one pointer twice as fast as the other. When the fast pointer reaches the end, the slow one is at the middle. If the list has a cycle, the fast one eventually laps the slow one and they meet.
Starting one pointer k steps ahead finds the k-th node from the end in a single pass, the gap stays constant as both walk.
Same idea detects cycles and then finds the cycle entrance by resetting one pointer to the head.
What you will be able to do
- Guard fast.next before advancing
- Reason about where the pointers meet
When to use it
- Detect a cycle
- Middle of the list
- N-th node from the end in one pass
2See it
Walkthrough
Cycle detection
1 → 2 → 3 → 2 …, slow +1, fast +2 until they meet.
1 / 6
List cycles 3→2. slow = fast = head. Compare references, not values.
Live template
Line 1 active
Complexity: time O(n), space O(1)
One pass O(n) time, O(1) space, better than counting length then walking again. Cycle detection is the same bound. Converting to an array is O(n) space and usually unnecessary.
Read the walkthrough as text
Middle of the list. 1 → 2 → 3 → 4 → 5.
slowandfaststart at1.- Each step:
slowmoves one,fastmoves two. - When
fastlands on5(or its next is None),slowis on3, the middle.
For even length 1..4, the usual convention lands slow on the second middle (3) or first (2) depending on the loop condition, match the problem statement.
3Recognise it
Kinds of problems (7)
Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.
Cycle detection
Example. Does a linked list have a cycle?
How. Slow +1, fast +2; cycle ⇔ they meet before fast hits None.
Start of the cycle
Example. Return node where the cycle begins.
How. After meeting, reset one pointer to head; advance both by 1 until they meet again.
Middle node
Example. Return middle of list (second middle if two).
How. When fast reaches end, slow is at middle; stop when fast.next is None.
N-th from the end (gap pointers)
Example. Remove n-th node from end in one pass.
How. Advance fast n steps ahead; then move both until fast is past the last node.
Palindrome linked list
Example. Is the list a palindrome (O(1) space)?
How. Find middle, reverse second half, compare halves, optionally restore.
Cycle detection on an index-linked array (find the duplicate)
Example. Array of n+1 values in 1..n, find duplicate.
How. Treat index as node, value as next pointer; Floyd’s algorithm on the implicit graph.
Pointers that switch heads (list intersection)
Example. Intersection node of two lists.
How. Two walkers swap to the other head when they exhaust a list; they meet at intersection or None.
Common mistakes
Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.
Null fast pointer
Why it happens. Advancing fast twice without checking fast.next first.
How it fails. fast = fast.next.next when fast.next is None, AttributeError on the last node.
Fix. Loop condition `while fast and fast.next:` before advancing slow once and fast twice.
Extra memory
Why it happens. A visited set detects cycles but ignores O(1) space requirements.
How it fails. Cycle check with `seen`, correct answer but fails follow-up “constant memory”.
Fix. Use Floyd: slow +1, fast +2; meeting inside the loop implies a cycle.
Wrong middle
Why it happens. Fast stops one step early or late for even-length lists.
How it fails. Even list: problem wants first middle but fast stops when fast.next is None, you return the second middle.
Fix. Match the spec: `while fast and fast.next` → second middle; `while fast.next and fast.next.next` → first.
4Check yourself
Concept check
A short quiz on this lesson before you practise. Optional, and it does not gate coding.
Ready to practise?
Mastery comes from solving. The lesson is optional context.