C++ solution with explanation


  • 0
    K

    Solve the problem in 2 steps:

    1. Check if there is a cycle in the list. Define two pointers,walker and runner. Walker takes one step at a time. Runner takes two steps at a time.Two pointers will meet if there is a cycle.
    2. Find the beginning of the cycle. In the first step, walker takes s1 steps, and runner takes s2 steps. The distance between the beginning of the list and the beginning of the cycle is d1. The length of the cycle is d2. The distance between the beginning of the cycle and the meeting point is c
      s2=2s1
      s2-s1=n
      d2
      s1=d1+c
      so
      n*d2=d1+c
      d1=(n-1)*d2+(d2-c)
      Define two pointers, each one takes one step at a time. Pointer 1 starts from the beginning of the list, Pointer 2 starts from the meeting point. If pointer 1 takes d1 step, pointer 2 takes (n-1)*d2+(d2-c) steps. Both of the pointers reach beginning of the cycle.
    class Solution {
    public:
        ListNode *detectCycle(ListNode *head) {
            if(head==NULL||head->next==NULL) return NULL;
            ListNode *walker=head,*runner=head;
            while(walker&&runner&&runner->next)
            {
                walker=walker->next;
                runner=runner->next->next;
                if(walker==runner) break;
            }
            if(walker!=runner) return NULL;
            walker=head;
            while(walker!=runner)
            {
                walker=walker->next;
                runner=runner->next;
            }
            return walker;
        }
    };

Log in to reply
 

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