Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
Follow up:
Can you solve it without using extra space?
1 class Solution {
2 public:
3 bool isCycle(ListNode* head) {
4 if (!head) {
5 return false;
6 }
7 ListNode* slow = head;
8 ListNode* fast = head;
9 while (slow && fast) {
10 slow = slow->next;
11 if (!fast->next) return false;
12 fast = fast->next->next;
13 if (fast == slow) {
14 return true;
15 }
16 }
17 return false;
18 }
19
20 ListNode *detectCycle(ListNode *head) {
21 if (!isCycle(head)) return NULL;
22 ListNode* dummy = new ListNode(0);
23 dummy->next = head;
24 ListNode* slow = dummy;
25 ListNode* fast = dummy;
26 while (slow && fast) {
27 slow = slow->next;
28 fast = fast->next->next;
29 if (slow == fast) {
30 break;
31 }
32 }
33
34 slow = dummy;
35 while(slow != fast) {
36 slow = slow->next;
37 fast = fast->next;
38 }
39 return slow;
40 }
41 };