Find start of loop of a link list - Floyds cycle detection algorithm

Question

I am trying to write code to detect the start of a loop using Floyds cycle detection algorithm. My link list is like this

1->2->3->4->5->6
         |_____|

This is the code I am using

bool findCycle(Node* root)
{
    auto slow = root;
    auto fast = slow->next->next;
    while (slow != nullptr && fast != nullptr)
    {
        if (slow == fast)
        {
            //Yes there is a loop. Lets find the start of the loop
            //Move slow to the head again and move by one pointer each.
            slow = root;
            while (slow != nullptr && fast != nullptr)
            {
                if (slow != fast)
                {
                    slow = slow->next;
                    fast = fast->next;
                }
                else
                {
                    std::cout << "The loop starts at node " << slow->val;
                    return true;
                }
                
            }
          
            
        }
        slow = slow->next;
        fast = fast->next->next;
    }
    return false;
}

I have managed to detect the loop at 5. At that point I move the slow pointer to the head and keep the faster pointer at 5. Now I move each pointer by 1 and I expect them to cross at a specific node but they never cross. Is my algorithm wrong ? What am I doing wrong.

If both pointers are moving at the same speed but start at different points, how would you ever expect them to cross? — Mark Ransom, Apr 12 '21 at 17:51
https://stackoverflow.com/questions/2936213/explain-how-finding-cycle-start-node-in-cycle-linked-list-work — James Franco, Apr 12 '21 at 17:57
Check out the most upvoted answer. I am trying to figure this out using Floyds — James Franco, Apr 12 '21 at 17:58
So your outer loop sequence is 1,3 2,5 3,4 4,6 5,5 at which point you've detected a loop. Your inner loop goes 1,5 2,6 3,4 4,5 at which point your `while` loop will be infinite because the pointers will never meet up. The link you gave is interesting but I'm not sure I can trust the answers since you seem to have a compelling counter-example. — Mark Ransom, Apr 12 '21 at 18:51

selbie · Answer 1 · 2021-04-12T18:56:36.747

I'm not sure if this is "Floyd's algorithm", but you can do some counting of the loop size to help out.

The moment you detect there is a loop with your loop detection algorithm, count how many elements there are in the loop:

// upon discovering that you are "in the loop"
Node* loop = current;
int count = 1;
current = current->next;
while (current != loop) {
    count++;
    current = current->next;
}

Now that you know the count of elements in the loop, set up another traversal from the start as follows

previous = root;
current = root;
lookahead = root;
for (int i = 0; i < count; i++) {
    lookahead = lookahead->next;
}

Then traverse in count sized jumps until you redetect the cycle:

while (current != lookahead) {
    previous = current;
    current = lookahead;
    for (int i = 0; i < count; i++) {
        lookahead = lookahead->next;
    }
}

When the loop exits, previous will be within count elements outside the start of the loop. So then we can traverse with one pointer going "one by one" and the other incrementing in count elements.

    current = previous;
    lookahead = previous;

    for (int i = 0; i < count; i++) {
        lookahead = lookahead->next;
    }

    while(current != lookahead) {
        current = current->next;
        current = current->next;
        
        for (int i = 0; i < count; i++) {
            lookahead = lookahead->next;
        }
    }

When the above loop exits, current points to the start of the loop. I think there is a way to optimize that last loop

score -1 · Answer 2 · answered Apr 12 '21 at 18:03

The first part of the algorithm given in Wikipedia is:

def floyd(f, x0):
    # Main phase of algorithm: finding a repetition x_i = x_2i.
    # The hare moves twice as quickly as the tortoise and
    # the distance between them increases by 1 at each step.
    # Eventually they will both be inside the cycle and then,
    # at some point, the distance between them will be
    # divisible by the period λ.
    tortoise = f(x0) # f(x0) is the element/node next to x0.
    hare = f(f(x0))
    while tortoise != hare:
        tortoise = f(tortoise)
        hare = f(f(hare))

You forgot to advance slow once as the first step.

The line

    auto slow = root;

should be:

    auto slow = root->next;

do u mean when i find the loop and move slow point to the head I need to move it one step again ? — James Franco, Apr 12 '21 at 18:10
@JamesFranco No. The "move the slow pointer to head" part in Wikipedia is `tortoise = x0`. No extra step is needed here. — MikeCAT, Apr 12 '21 at 18:11

Find start of loop of a link list - Floyds cycle detection algorithm

2 Answers2