interview/linkedListCycle.cpp at master · taohi/interview · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/*
 *   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==NULL||head->next==NULL)
                return NULL;
            ListNode *fast=head;
            ListNode *slow=head;
            ListNode *meet=NULL;
            ListNode *cycle_start=NULL;
            bool hasCycle=false;
            while(fast!=NULL && fast->next!=NULL)
            {
                fast=fast->next;
                fast=fast->next;
                slow=slow->next;
                if(slow==fast)
                {
                    meet=slow;
                    hasCycle=true;
                    break;
                }
            }
            if(has==false)
                return NULL;
            slow=head;
            while(slow!=meet)
            {
                slow=slow->next;
                meet=meet->next;
            }
            cycle_start=slow;
            return cycle_start;
        }
};