141. 环形链表：哈希集合判圈

遍历链表时，把每个访问过的节点地址加入集合。若当前节点已存在于集合中，说明沿 next 指针回到了此前位置，链表存在环。

1
/**
2
 * Definition for singly-linked list.
3
 * struct ListNode {
4
 *     int val;
5
 *     ListNode *next;
6
 *     ListNode(int x) : val(x), next(NULL) {}
7
 * };
8
 */
9
class Solution {
10
public:
11
    typedef struct ListNode* PtrtoNode;
12
    bool hasCycle(ListNode *head) {
13

14
        set<PtrtoNode> s;
15

16
        while(head != NULL) {
17
            if(s.count(head)) return 1;
18
            s.insert(head);
19
            head = head->next;
20
        }
21

22
        return 0;
23
    }
24
};

没有环时会遍历到 nullptr；有环时会再次访问某个节点。时间复杂度为 $O(n)$ ，额外空间为 $O(n)$ 。