题解 | #判断链表中是否有环#

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

/**
1. 利用快慢指针来判断链表是否存在环
2. 将链表结点依次压入vector中，然后遍历链表
3. 哈希表unordered set（因为有find，并且不自动排序,不允许重复数据）这里ListNode每一个虽然val相同，但是本身不同
*/
class Solution {
public:
    bool hasCycle(ListNode *head) 
    {
        // 用Hash表，遍历链表节点，先判断表中是否已经存在
        // 如果存在就是证明有环，不存在就将节点保存进Hash表
        unordered_set<ListNode*> us;
        while (head)
        {
            if (us.find(head->next) != us.end())
            {
                // cout << *us.end() << endl;
                return true;
            }
            else 
            {
                us.insert(head);
                head = head->next;
            }
        }
        return false;
    }
};