141.环形链表.md

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

// 复习

// 此题最直观是利用哈希表find的特性，查找复杂度为O(1)。
// while遍历链表过程中，将每个node地址装入哈希set中，然后判断遇到的node地址是否出现过（即是否
// 存在于哈希set中，如果存在即时环形）。

// 几个需要注意的点：
// 1）对于这种哈希set的insert和find来判断是否出现的问题，需要先find来判断，然后再insert。
// 因为这样顺序才是对的，否则先insert了，那find岂不是就直接有了。先find则第1次出现没有，insert后，
// 如果第2次再出现，那find就有了。

// 2）此题哈希set没任何问题，即使node值相等，但node的地址是唯一的，我们装的是node的地址。 

class Solution {
public:
    bool hasCycle(ListNode *head) {
        unordered_set<ListNode*> un_set;
        ListNode* cur = head;
        while (cur) {
            // if (un_set.find(cur) != un_set.end()) {
            // 这两种写法都可以，都是判断哈希set里是否已存在某个key值
            if (un_set.count(cur)) {
                // 一旦查到相同的，说明之前已经装过了，返回true。
                return true;
            }
            un_set.insert(cur);
            cur = cur->next;
        }
        // 如果链表能够遍历结束，说明不是环形链表，返回false。
        return false;
    }
};