Two pointers walk a linked list at different speeds. If there is a loop the fast one catches the slow one, and when the fast one hits the end the slow one is in the middle.
Used for
both start at node 1
slow + 1, fast + 2
same node: there is a loop
This list has no loop. What does the fast walker reach first?
Not quite. With no loop there is nothing to catch it, so fast reaches the end first. That also tells you the list has no cycle.
Step 1 of 6
Question: does this chain of nodes loop back on itself? Walking it one node at a time never answers that, because inside a loop you just keep going. Instead send two walkers from the start: a slow one moving 1 node per step and a fast one moving 2.
Step 2 of 6
After one step the slow walker is on node 2 and the fast one on node 3.
Step 3 of 6
Again: slow on 3, fast on 5, the last node.
Step 4 of 6
The last node points back to 3, so fast carries on 5 → 3 → 4 while slow steps to 4. They land on the same node.
Step 5 of 6
Why they must meet: inside a loop the fast walker gains one node on the slow one every step, so it catches up. Without a loop, fast would simply fall off the end (null) first. Two walkers at different speeds is called fast and slow pointers.
Step 6 of 6
Your turn.
Linked List TraversalDoubly Linked ListLinked ListDetect Cycle in Graphs
function hasCycle(head) { let slow = head, fast = head; while (fast && fast.next) { slow = slow.next; fast = fast.next.next; if (slow === fast) return true; } return false;}