141. 环形链表

题目描述：给定一个链表，判断链表中是否有环。

Solution1:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    bool hasCycle(ListNode *head) {
        std::set<ListNode*> node_set;
        while(head){
            if(node_set.find(head) == node_set.end()){
                node_set.insert(head);
            }else{
                return true;
            }
            head = head->next;
        }
        return false;
    }
};
思路：

使用set。
将每一个结点在set中检查，如果没有，就插入该结点。如果找到了，就说明有环。如果到头了，说明没环，返回false；

该方法由于使用了set，所以空间复杂度为O(n);

Solution2：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bool hasCycle(struct ListNode *head) {
    struct ListNode *slow = head;
    struct ListNode *fast = head;
    while(fast){
        slow = slow->next;
        fast = fast->next;
        if(fast){
            fast = fast->next;
        }else{
            return false;
        }
        if(slow == fast){
            return true;
        }
    }
    return false;
}

思路：

使用双指针。
用两个移动速度快慢不相同的指针来判断是否有环。如果有环，两个指针终会相遇，返回true。

由于快指针一定在慢指针的前面，所以在移动指针时，只要判断快指针是否为空，如果是，就说明没有环。返回false；