We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
At this point one of two things are true: 1) the linked list does not loop (checked with fast != null && fast.next != null) or 2) it does loop. Let's continue visualization assuming it does loop:
If the linked list is not looped, the fast pointer finishes the race at O(n/2) time; we can remove the constant and call it O(n). If the linked list does loop, the slow pointer moves through the whole linked list and eventually equals the faster pointer at O(n) time.
Cycle Detection
You are viewing a single comment's thread. Return to all comments →
The tale isn't important.
There is a "slow" pointer which moves one node at a time. There is a "fast" pointer which moves twice as fast, two nodes at a time.
A visualization as slow and fast pointers move through linked list with 10 nodes:
At this point one of two things are true: 1) the linked list does not loop (checked with
fast != null && fast.next != null
) or 2) it does loop. Let's continue visualization assuming it does loop:If the linked list is not looped, the fast pointer finishes the race at O(n/2) time; we can remove the constant and call it O(n). If the linked list does loop, the slow pointer moves through the whole linked list and eventually equals the faster pointer at O(n) time.