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] 
       [#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 {
            ListNode *detectCycle(ListNode *head) {
                ListNode* dummy=new ListNode(-1);
                ListNode *slow=dummy, *fast=dummy;
                bool flag=false;
                while(fast && fast->next){
                    if(fast==slow)  { flag=true; break; }
                if(!flag)   return NULL;
                ListNode* result=dummy;
                while(result != slow){
                    slow=slow->next;**strong text**
                return result;

  • 0

    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
    This post is deleted!

  • 2

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

  • 0

    @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.