Logic behind the method to identify cycle in a linked list

Question

In the best method to detect a cycle in a linked list, we do the following:

1. Use Floyd's Cycle-Finding Algorithm and identify a position within the cycle in a linked list.
2. Count the size of the cycle in the linked list
3. Position one pointer at the beginning of the list and another 'k' (where k is the size of the cycle) positions away.
4. On iteration they meet at the beginning of the cycle.

I'd like to know why this works. Some theoretical logic behind this?

• Doc Brown: Perhaps you are intermixing "loop" and "linked list" in your description?
• Cameron: Generally, a "loop" refers to a construct that iterates, whereas you seem to be concerned with "cycles" in a linked-list. Just so you know.
• Aks: yep. I mean cycle. thanks for clarifying
• Paul R: It seems kind of obvious - maybe draw a diagram if it's not clear ?
• Aks: I get that it works. I'm just not clear how it was arrived at

Answer 1

Floyd method helps you detect that there's a cycle, but because there may exist some nodes before start of cycle, it can not directly give you the length of cycle. So you should calculate the length in the next step. Now we want to spot start point of cycle. Consider, length of cycle is K and number of nodes from head node to start of cycle is L, now if you move both pointers forward, they meet at the start of cycle, because, the head pointer has to go forward L nodes and the pointer which K steps ahead has two possibilities. It sure will be on start of cycle after L node because: Choice 1: if it is in cycle, it's on the node K-L of cycle and K-(K-L) = L. Choice 2: if it is out of cycle, L-K nodes is remaining to the start and L-K + K = L.

• Aks: what does K-(K-L) = L signify?
• saeedn: @Aks That when cycle length is K and you are on node K-L, there are L nodes ahead to reach start of cycle (exactly the same for the node starting from head of linked list).
• Aks: how did you arrive on the fact that the node is on K-L of the cycle
• saeedn: @Aks Part 3 says that pointer is K positions away, so if we assume there are L nodes from head to start of cycle, the pointer is on node K-L (L nodes from K steps are used to reach start of cycle)