LeetCode/142.cpp at master · nitin-maharana/LeetCode · 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
44
45
46
47
48
49
50
51
/*
 * Written by Nitin Kumar Maharana
 * nitin.maharana@gmail.com
 */

/**
 * 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 == nullptr)
            return nullptr;

        ListNode *slow, *fast;

        slow = fast = head;

        while(1)
        {
            if(slow->next == nullptr)
                return nullptr;

            slow = slow->next;

            if(fast->next == nullptr || fast->next->next == nullptr)
                return nullptr;

            fast = fast->next->next;

            if(slow == fast)
                break;
        }

        slow = head;

        while(1)
        {
            if(slow == fast)
                return slow;

            slow = slow->next;
            fast = fast->next;
        }
    }
};