C++ implementation with much more clear and strict explanation ! any one can give more clear ?


  • 17

    Just use the dummy head pointer and why first find the meeting point and then set the result-pointer at the dummy and move forward to find the result position.
    There are the reasons :

    set the

       [#cycle length = C ]  
    
       [#length-from-head-to-cycle-start-point = L] 
    
       [#cycle-start-point-meeting-point=S] 
    
       [#meeting-point-clock-direction-to-cycle-start-point=Y]
    
       [#step needed to meeting=T]
    

    Then when they meet, we have

       2 * T = T + N1 * C    N1=0,1,2...
    

    so we get

       T = N1 * C
    

    Also we have

       2 * T = L + N2 * C + S    N2=0,1,2...
    

    we can get

       N3 * C = L + S  with C = S + Y   N3 = 2 * N1 - N2
    

    so we have

      (N3 - 1) * C + S + Y = L + S
    

    then we have

      (N3 - 1) * C + Y = L
    

    just means that we can do the things that have been explained by others.

    We can move a node from head and node from the meeting point, then when they meet, it is the

    start point of the cycle.

    Here is the code :

    class Solution {
        public:
            ListNode *detectCycle(ListNode *head) {
                ListNode* dummy=new ListNode(-1);
                dummy->next=head;
                ListNode *slow=dummy, *fast=dummy;
                bool flag=false;
                while(fast && fast->next){
                    slow=slow->next;
                    fast=fast->next->next;
                    if(fast==slow)  { flag=true; break; }
                }
                if(!flag)   return NULL;
                ListNode* result=dummy;
                while(result != slow){
                    result=result->next;
                    slow=slow->next;**strong text**
                }
                return result;
            }
        };

  • 0
    Y

    @RainbowSecret
    why have to use a flag here?
    I thought just check fast is null or not is good enough to know whether this is a cycle list.
    However, it turns out it doesn't work at all.
    Do you know why we have to use flag here?

     ListNode *detectCycle(ListNode *head) {
            if(!head || !head->next) return nullptr;
    
            ListNode *fast(head), *slow(head);
            while(fast && fast->next){
                fast = fast->next->next;
                slow = slow->next;
                if(fast == slow) break;
            }
            if(!fast) return nullptr; // No cycle
            
            // Right now fast and slow meet.
            fast = head; // let fast begin from head
            while(fast != slow){
                fast = fast -> next;
                slow = slow -> next;
            }
            
            return fast;
        }
    

  • 0
    W
    This post is deleted!

  • 2
    W

    @yang121
    or example:
    1->2->3 this is no cycle
    1、slow=head;fast=head(slow->val=1,fast->val=1)
    2、slow=head->next,fast=head->next->next(slow->val=2,fast->val=3)
    then break
    but fast!=NULL so the code will not executed if(!fast) return nullptr; // No cycle


  • 0
    L

    @yang121 change " if(!flag) return NULL; " to " if(!flag || !flag->next) return NULL;"


Log in to reply
 

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