IntermediateLinked List
Fast and slow pointers
Move one pointer 1 step and another 2. In a cycle they must meet; in a straight list the fast one stops at the end, the slow one at the middle.
The idea
Two pointers moving at different speeds reveal the shape of a linked list without extra memory. If there's a cycle, the fast pointer laps the slow one and they meet. If there isn't, the fast pointer reaches the end.
When fast reaches the end, slow has gone half as far: it's at the middle.
Worked example
Middle of 1 → 2 → 3 → 4 → 5
- slow 1, fast 1 → slow 2, fast 3 → slow 3, fast 5 → fast can't move two more → middle is 3
In code (Python)
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow, fast = slow.next, fast.next.next
if slow is fast:
return True
return False
def middle(head):
slow = fast = head
while fast and fast.next:
slow, fast = slow.next, fast.next.next
return slowO(n) time, O(1) space.
How to spot it
- Cycle detection, the middle node, “find the duplicate number” in an array treated as a list.
Common mistakes
- Checking `fast.next.next` without checking `fast.next` first.
- Comparing values instead of the nodes themselves.
Practise it
Go further
Up next for you · Beginner
“Have I seen this?” is a set →