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.
Let f(i) = the memory address of the node that is a distance i from the head of the list. So f(0) = head, f(1) = head->next, and so on. If there is a cycle of length L that starts at node N in the list, then f(i) = f(i + kL) for all i >= N and all k >= 0 by periodicity.
In particular, assuming the slow and fast pointers meet, we have f(i) = f(2i) which means that 2i = i + kL or i = kL. So the slow pointer is equal to the fast pointer for all values of i = kL where kL >= N. The first time they meet is the smallest such kL.
So my earlier statement isn't strictly true the way that I wrote it -- if N is much larger than L, then the fast pointer will spin around in the cycle several times while it waits for the slow pointer to just reach the start of the cycle. But once the slow pointer does get to the cycle, it will reach the smallest kL >= N somewhere during its first traversal around the cycle. Since the fast pointer is going twice at fast, it will only travel around the cycle at most twice during this time.
The time complexity is O(kL) = O(N + L); that is O(N) for the slow pointer to reach the cycle, plus O(L) for the slow pointer to reach the meeting point somewhere during its first time around the loop.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Linked Lists: Detect a Cycle
You are viewing a single comment's thread. Return to all comments →
Let f(i) = the memory address of the node that is a distance i from the head of the list. So f(0) = head, f(1) = head->next, and so on. If there is a cycle of length L that starts at node N in the list, then f(i) = f(i + kL) for all i >= N and all k >= 0 by periodicity.
In particular, assuming the slow and fast pointers meet, we have f(i) = f(2i) which means that 2i = i + kL or i = kL. So the slow pointer is equal to the fast pointer for all values of i = kL where kL >= N. The first time they meet is the smallest such kL.
So my earlier statement isn't strictly true the way that I wrote it -- if N is much larger than L, then the fast pointer will spin around in the cycle several times while it waits for the slow pointer to just reach the start of the cycle. But once the slow pointer does get to the cycle, it will reach the smallest kL >= N somewhere during its first traversal around the cycle. Since the fast pointer is going twice at fast, it will only travel around the cycle at most twice during this time.
The time complexity is O(kL) = O(N + L); that is O(N) for the slow pointer to reach the cycle, plus O(L) for the slow pointer to reach the meeting point somewhere during its first time around the loop.