Straight Forward C++ Solution with Explanation by using 2-Pointers (16ms)


  • 4
    K
    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        ListNode *detectCycle(ListNode *head) {
            if(!head) return NULL;
            ListNode *p1=head;
            ListNode *p2=head;
            int count=0;    //using count to record the length of cycle, if it exists.
            while(p1&&p2){
                count++;
                p1=p1->next;
                p2=p2->next;
                if(p2!=NULL) p2=p2->next;
                if(p1==p2&&p1&&p2){
                    p1=head;
                    p2=head;
                    //make the distance between p1 and p2 be the length of cycle
                    //when p1 and p2 meet at the first time, this postion will be the start node of the cycle.
                    for(int i=0;i<count;i++) p2=p2->next;   
                    while(p1!=p2){
                        p1=p1->next;
                        p2=p2->next;
                    }
                    return p1;
                }
            }
            return NULL;
        }
    };

  • 0
    H

    why the counter can record the length of cycle?


  • 0
    K

    p2 is moving one step faster than p1 each time.When p1 and p2 meet again, p2 is k step ahead of p1, here k is exactly the length of the circle. The count variable here is used to calculate the k.


  • 0
    N

    I'm having the same question and I keep having trouble understanding the reply:

    Let the list be represented as 2 segments: an arbitrary length m and a section of length n, where the cycle begins at index m.

    After slow has reached m, it takes another arbitrary k steps for slow to meet fast again. By now slow has traveled m+k steps, meets fast at position m+t where t is in range of 0...n-1. At the same time fast has travelled 2m+2k steps.

    According to the code above, the difference should be m+k steps. After the second loop when they meet again, why will they meet at the beginning of the loop?


  • 0
    V

    I think the count variable may not be equal to k. But it must be the integral multiple of k.


  • 0
    B

    Actually, count is integral multiple of loop length


Log in to reply
 

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