Why Floyd's cycle finding algorithm, the tortoise and hare both need to start at the same location?

Question

I understand that why tortoise and hare will meet if hare moves at speed 2 and tortoise moves at speed of 1 if there is one cycle. Because if the cycle length is k, the (2-1)*t (distance between tortoise and hare) will eventually be dividable k. But what I don't understand is why in order to find the entry point both tortoise and hare need to start at the same location in the beginning.

Here is what I implemented correctly. But just by changing the initial condition the finding of entrance point will loop forever.

    if(!head || head->next==nullptr) return nullptr;
    ListNode* fast=head->next->next; 
    ListNode* slow=head->next; // if changing to slow=head or fast=head->next the second loop below will loop forever.
    while(fast!=nullptr && fast->next!=nullptr
        && slow!=nullptr && fast!=slow) {
        fast = fast->next->next;
        slow = slow->next;
    }
    if(fast!=nullptr && slow!=nullptr && fast==slow) {
        slow = head;
        while(fast!=slow){
            fast = fast->next;
            slow = slow->next;
        }
        return fast;
    } else { 
        return nullptr;
    }

---

I found out the answer myself:

Assume the circle length is n, the length from start to the entry point of circle is k, the first loop took time t till both pointers meet.

We will have (2t-k) = (t-k) (mod n), where 2t-k is the hare's distance on the circle and t-k is the tortoise's distance on the circle.

Let's say tortoise have moved q=t-k on the circle. Using modular arithmetic

t = 0 (mod n)
q+k = 0 (mod n)

Let's define int l>=0 so that q+k=l*n. k=l*n-q which means the distance k from start to the entry point is the distance tortoise going forward with length l*n-q which also arrive at the entry point. #

Please point out anything if I am wrong.

Answer 1

If the tortoise and the hare are in the same cycle, they will meet. Starting from different locations, the loop running forever means the tortoise and the hare are in different cycles.

Edit: Looking at your code, it looks like your 2nd loop is running forever, not the first one.

Your 2nd while loop is fundamentally wrong. At the beginning of that loop, if fast and slow start at the same location, it will just exit. If not, it might run forever (which is probably what happened).

Answer 2

Let N be the number of steps the tortoise takes before the tortoise and hare meet. Let C be the number of nodes in the cycle. Call the node where they meet X.

If the tortoise and the hare start at the same point, then when they meet, the hare will have traversed N steps further along the cycle than the tortoise. For the tortoise and hare to be at the same node at this point, N must be a multiple of C.

If you were to then place the tortoise back where it started and move the tortoise and the hare both N steps forward (at equal paces this time), then the tortoise and hare would be at node X again - the tortoise because N steps is how far it traversed to get there originally, and the hare because N is a multiple of C.

For this to be the case, with both the tortoise and the hare moving at the same pace, they would have to be at the same node as soon as the tortoise enters the cycle. So if you place the tortoise back at the start of the list, and advance the tortoise and the hare at equal paces until they meet, then they will meet at the start of the cycle.

---

That was all for if the tortoise and the hare start at the same position, though. If you start them at different positions, this changes where they meet. The hare will be in the wrong position for the second loop. Instead of the tortoise and the hare being at the same node when the tortoise re-enters the cycle, they'll be offset from each other, and they'll never meet again.

Answer 3

Premise

Assume that hare and tortoise can enter the same cycle, the number of the nodes is n, the distance between hare and tortoise's is x after they both entered the cycle, then after t steps, the distance between hare and tortoise is x + 2 * t - t = x + t. Because t is increased by 1 every time the first loop runs, there must be once that x + t is a multiple of n, therefore it means hare is exactly a few laps a head of tortoise, that means that hare and tortoise meets.

Conclusion 1: hare and tortoise must meet somewhere in the first loop.

---

Explanation

In the cycle

As you can see from the code, the first loop ensures that fast == slow. In the second loop, the code sets tortoise to the start. If head != fast, the second loop would run. But in the second loop, the speed of hare and tortoise is the same, and that means that the relative position of hare and tortoise would never change. Therefore they wouldn't meet, then the loop runs forever.

So, what kind of condition determines whether head == fast in the second loop? As we know, after the first loop, fast == slow. Therefore, the position of hare is the position where tortoise and hare met.
If the initial location of tortoise and hare isn't the same, that means the x mentioned in the first paragraph isn't 0 so it wouldn't be a multiple of n. Because at the first loop x + t is a multiple of n, then t isn't a multiple of n.
Then because when the first loop ends, the distance between tortoise and start should be just t and t isn't a multiple of n, the location of tortoise and start isn't the same. As tortoise and hare meets at the same place, the location of hare and start isn't the same too. Then head != fast.

With the same idea, we can know:

1. If the initial location of slow and fast isn't the same, then head != fast at the second loop.
2. If the initial location of slow and fast is the same, then head == fast at the second loop.

We can see from the second paragraph, with the first case, the second loop runs forever. But with the second case, every thing works fine.

Conclusion 2: whether tortoise and hare starts at the same place affects whether the second loop runs forever because of a math reason.

---

Overall

Let's consider an overall situation: (Assume that the hare and the tortoise starts at the same position)

Setup

Define that the distance from the start point to the entry point is a, the length of the cycle is n and it takes t steps for the hare to catch up with the tortoise after the tortoise entered the cycle.

For example, in the following map:

start point
|     entry point
V     V
0->1->2->3->4->5
      |        |
      \--------/

a equals to 2, n equals to 4 and t equals to 2.

We call the distance from the entry point to a node the node's position. The position can be represented like x % n.

Simulation

Let's simulate the race:

1. First race
   1. When the tortoise goes to the entry point, the hare's position is (2a - a) % n = a % n and the tortoise's position is 0. Their distance is a.
   2. After t steps, the hare catches up with the tortoise. At this time their distance a + t should be a multiple of n.
   3. Their meeting point's position is t % n as the tortoise moved t steps.
2. Second race
   1. The tortoise goes back to the entry point. The position of the hare is t.
   2. They starts to move at the same speed.
   3. When the tortoise gets to the entry point, it went a steps. At this time, the hare also moved a steps, so its position now is (t + a) % n. Because a + t is a multiple of n, so the hare's position is 0. That means it is at the entry point. So they meet.

Conclusion 3: if tortoise and hare starts at the same position, they meets at the entry point at the end of the second race.

Conclusion

Conclusion of 3 Conclusions

1. hare and tortoise must meet somewhere in the first loop.
2. whether tortoise and hare starts at the same place affects whether the second loop runs forever.
3. if tortoise and hare starts at the same position, they meets at the entry point at the end of the second race.

But what I don't understand is why in order to find the entry point both tortoise and hare need to start at the same location in the beginning.

Yes.
As we can see from Conclusion 3, this initialization is correct.
As we can see from Conclusion 2, other situation probably lets the second loop runs forever.
To let the code work at every situation, both tortoise and hare need to start at the same location in the beginning. This actually is a math simulation that can be proved by paper and pencil.

_{Related:
How does finding a cycle start node in a cycle linked list work?
How would I find an infinite loop in an array of pointers?
Wikipedia}