Linked List Cycle II

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用extra space来存hash table。不然就用Floyd's method。

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.

http://www.geeksforgeeks.org/detect-and-remove-loop-in-a-linked-list/

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

Code:

Method 2:

    ListNode *detectCycle(ListNode *head) {

        if(head==NULL) return NULL;
        bool hasCycle=false;

        ListNode *slow, *fast;
        slow=fast=head;
        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++;
        }

        slow=fast=head;
        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:
    ListNode *detectCycle(ListNode *head) {
        unordered_set<ListNode *> visited;
        return DFS(head, visited);
    }

    ListNode *DFS(ListNode *head, unordered_set<ListNode *>& visited){
        // meet visited node, return it
        if(visited.find(head)!=visited.end()) return head; 

        // come to end, NULL, means no cycle, return NULL
        if(head==NULL) return NULL;

        visited.insert(head); // Mark as visited
        return DFS(head->next, visited);
    }
};