LeetCode #142

# Description:

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Note: Do not modify the linked list.

Follow up: Can you solve it without using extra space?

## Example:

``````Note
``````

# Idea:

DP method: hash unordered_set记录node是否已经visited，如果不是，标注为visited，如果下一步遇到visited，说明是cycle的起点。

Note: This so-called Floyd's Cycle finding algorithm could also work.

To detect the loop, have one pointer move 1 step a time, another pointer move 2 steps a time. If they meet each other, means cycle exists.

We do not need to count number of nodes in Loop. After detecting the loop, if we start slow pointer from head and move both slow and fast pointers at same speed until fast don’t meet, they would meet at the beginning of linked list.

Method 2: 比较巧妙，time O(n), 先找到cycle上的点。再计算cycle长度k。然后两个pointer，一个先advance k step.然后两个相交的地方就是cycle的起点。

# Code:

Method 2:

``````    ListNode *detectCycle(ListNode *head) {

bool hasCycle=false;

ListNode *slow, *fast;
while(fast!=NULL && fast->next!=NULL){
slow=slow->next;
fast=fast->next->next;
if(slow==fast){
hasCycle=true;
break;
}
}
if(!hasCycle) return NULL;

int k=1;
while(fast->next!=slow){
fast=fast->next;
k++;
}

for(int i=0; i<k; i++){
fast=fast->next;
}
while(slow!=fast){
slow=slow->next;
fast=fast->next;
}
return slow;
}
``````

DP method:

``````class Solution {
public:
unordered_set<ListNode *> visited;
}

ListNode *DFS(ListNode *head, unordered_set<ListNode *>& visited){
// meet visited node, return it