Why in Floyd's Algorithm for cycle detection if we take fast as head.next than the solution becomes wrong?

102 Views Asked by At

So I was solving leetcode's question where we have to return the node where the tail connects, but the solution came wrong when I took fast = head->next and came right when I took fast = head. I understood how the latter was correct but I didn't quite understood why?

Example: Input: head = [3,2,0,-4], pos = 1 Output: tail connects to node index 1

wrong code

ListNode *slow = head, *fast = head->next;
    
    while(fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        
        if(slow == fast)
            break;
    }
    if(fast == NULL || fast->next == NULL){
        return NULL;
    }
    slow = head;
    while(fast != slow){
        slow = slow->next;
        fast = fast->next;
    }
    return fast;

correct code

ListNode *slow = head, *fast = head;
    
    while(fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        
        if(slow == fast)
            break;
    }
    if(fast == NULL || fast->next == NULL){
        return NULL;
    }
    slow = head;
    while(fast != slow){
        slow = slow->next;
        fast = fast->next;
    }
    return fast;
0

There are 0 best solutions below