Linked List Cycle

LeetCode #141

Description:

Given a linked list, determine if it has a cycle in it.

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

Example:

Note

Idea:

DP方法，几乎不用修改就可以找到cycle入口node。但是需要extra space。

另一种方法，两个pointer，一个走一步，一个走两步。如果meet就说明有cycle。

Code:

DP method.

class Solution {
public:
    bool hasCycle(ListNode *head) {
        unordered_set<ListNode *> visited;
        return DFS(head, visited);
    }

    bool DFS(ListNode *head, unordered_set<ListNode *>& visited){
        if(visited.find(head)!=visited.end()) return true;
        if(head==NULL) return false;

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

Method 2: 快慢pointer

class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode *slow, *fast;
        slow=fast=head;
        while(fast!=NULL && fast->next!=NULL){
            slow=slow->next;
            fast=fast->next->next;
            if(slow==fast){
                return true;
            }
        }
        return false;
    }
};