0

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;
  • You might find a hint at [Explain how finding cycle start node in cycle linked list work?](https://stackoverflow.com/q/2936213/5987). I'm sure it has something to do with the math that gives you the starting point of the cycle. – Mark Ransom May 08 '21 at 17:44
  • Does this answer your question? [Explain how finding cycle start node in cycle linked list work?](https://stackoverflow.com/questions/2936213/explain-how-finding-cycle-start-node-in-cycle-linked-list-work) – trincot May 09 '21 at 07:45

0 Answers0