What if it is a cycle linklist, which means all nodes are in the loop?


  • 0
    R

    so I don't know what would be the start of this loop ? and What for returning?
    Because I suppose it is avoided in the testing data, but the case [0, 1], and tail connect to head was included in the OJ data? How should I process it?

    Last executed input: {1,2}, tail connects to node index 0

    class Solution {
    public:
        ListNode *detectCycle(ListNode *head) {
            if(head==NULL) return NULL;
            ListNode* slow=head, *fast=head->next;
            while(slow!=NULL && fast !=NULL)
            {
                if(slow==fast) break;
                slow=slow->next;
                if(fast->next==NULL) return NULL;
                fast=fast->next->next;
            }
            
            if(slow==NULL || fast ==NULL) return NULL;
            ListNode* p=head;
            while(p!=slow)
            {
                p=p->next;
                slow=slow->next;
            }
            return p;
        }
        
    }
    

    ;


  • 0
    S

    If the list itself is a loop, then the slow and fast pointer will meet at the starting point (a.k.a 'head'). You should then move p to head, and now we have 'p == slow', so you know p (or 'head') is the 'first node' in the loop. It appears that your first while loop is problematic: you should let slow and fast both start from head, and probably need to move the break statement to the end of the while loop. Otherwise, the fast pointer would travel 2k+1 nodes while the slow pointer travels only k nodes, this could lead to wrong results.


  • 0
    R

    Thanks for your help, 2k and k would be correct, I can either put break in the end of while loop or chage to do while loop. Also it returns the head it meanningful, as from head, the first that are in the cyle is head node : )


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.