NC4 判断链表中是否有环

简介

刷题有一段时间了，但是整体的提升还是不大，做过的题目还是没有印象，当初做题的记住了，但是过了几天就发现忘记了，导致现在效率很低下。总结了有如下几个原因 :

1. 现在是刷题图的数量而不是质量，根本没有掌握核心的思想以及技巧，都是看一遍答案之后，短时间的明白了，但是一段时间过后还是忘记了，必须改变这种思维，更多的是精刷，掌握刷题的核心思想以及用到的技术点，通过理论的推导来实现。
2. 把每一道题到做每一次面试来练习，吃透这道题目。
3. 做过的题目提炼出面试的过程中能写出的代码，想清楚过程
4. 做题要有递归的思想，把复杂的问题拆解为一个个小问题，解决每一个小问题，最终大的问题就会解决
5. 刷各家公司高频面试题 codetop

题目

描述

判断给定的链表中是否有环。如果有环则返回true，否则返回false。
你能给出空间复杂度的解法么？
输入分为2部分，第一部分为链表，第二部分代表是否有环，然后回组成head头结点传入到函数里面。-1代表无环，其他的数字代表有环，这些参数解释仅仅是为了方便读者自测调试

这是一道高频题，典型的做法是使用快慢指针判断相等的解决办法，但是时间复杂度是O(n)，有没有更加高效的做法呢，判断重复问题最高效的就是哈希表处理，同理这道题目也用哈希表来处理。

class Solution {
public:
    bool hasCycle(ListNode *head) {
        unordered_set<int> hashset;
        while(head != NULL && head->next != NULL){
            head = head->next;

            if(hashset.count(head->val) == 1){
                return true;
            }
            hashset.insert(head->val);

        }
        return false; 
    }
};

其中一个测试用例不通过， 观察测试用例的构造，发现其中部分数据有重复，但是并不是环形的，而上面代码中的unordered_set 哈希表的类型是int,通过判断int val是否有重复显然是有Bug的，所以还是要改为 ListNode* 类型

另外写代码的过程中，发现针对 unordered_set.count 函数的用法并不是特别理解，以为是计算次数的，但是想想，哈希表中是没有重复数据的，故应该是判断数据是否存在的，

修改后正常提交

class Solution {
public:
    bool hasCycle(ListNode *head) {
        unordered_set<ListNode*> hashset;
        while(head != NULL && head->next != NULL){
            head = head->next;

            if(hashset.count(head) == 1){
                return true;
            }
            hashset.insert(head);

        }
        return false; 
    }
};