本文共 2465 字，大约阅读时间需要 8 分钟。

leetcode做题笔记，只记录个人的解题思路和学习理解过程。

题目描述：

给定一个链表，判断它是不是有环。 follow up： 系统推荐解决这个问题不使用额外的空间。

//链表的样子是这样的struct ListNode {      int val;      ListNode *next;      ListNode(int x) : val(x), next(NULL) {} };

1.作者开始的思路是很老套的：

因为他提示的tags中说明了用2个指针，而结合判断有环还是没环的特征，我想着是用两个指针one，two。 two每次走一步，在two走到了这一步时，使用one从head开始走，one每走一步，就执行一步判断one == two->next，如果是，返回true，不是，one继续走，直到它走到two的位置，同理判断two是不是指向自己。一次循环没了，到two刚才所在的这个地方是没有环的，那继续下一次循环，two前进一步，one又从头开始。 这里我给出自己的代码，不知道是逻辑出错还是其他原因，leetcode没通过：

//时间复杂度O(n^2)，空间复杂度O(1)bool hasCycle(ListNode *head) {        if(head == NULL || head->next == NULL)            return false;        if(head == head->next)//将一个元素是否指向自己的情况判断完了，下面直接从第二个元素开始            return true;        ListNode* one = head;        ListNode* two = head->next;        while(two->next)        {            one = head;            while(one != two)            {                if(one == two->next)                    return true;                else                    one = one->next;            }            if(one == two && one == two->next)//跳出循环时候one == two了，这时再判断是否指向自己                return true;            two = two->next;        }        return false;    }

希望大家能帮我找出代码中的错误，指正一下我，真诚感谢。

2.hash表的方法

上面这个比较的方法，其实按照leetcode给出的答案是等同于比较所有链表节点的地址，有相等的，就是有环，用hash的方法可以很简便地解出，建一个hash表存放节点地址，链表所有节点的地址从头开始加进去，如果遇到已经进去过的节点，那就说明回到了那个节点，也就是有环。

//时间复杂度O(n),空间复杂度O(n)bool hasCycle(ListNode *head) {        if(head == NULL || head->next == NULL)             return false;        unordered_map
   
     m;   //unordered_map
    
      m;        while(head != NULL)        {            if(m.find(head) != m.end())                return true;            else                m.insert(make_pair(head,100)); //map->insert(make_pair(key, value));             head = head->next;        }        return false;         }
    
   

另外提到一点，STL中hash表的用法还需要熟悉，有些特性需要记住，像自定义类型使用时需要重载某些运算符….等等

3.但是题目给出的提示是最好别开辟额外的空间，之后就看到了另外一种方法。

给出两个指针slow，fast。都是从head开始走，slow一次走一步，fast一次走两步。那这样一来，如果正常没环，fast会先走到null，而且slow在中间的位置。如果存在环，那就会是fast先进去环中，走了不知道几圈，slow才会进来

那就从slow进入到环的入口处开始考虑，两个人在一个环形的跑到中，一个跑得快，一个跑得慢，跑得快的总会追上跑得慢的，不管两者处在什么位置，中间相隔的距离总会一步步被追上。

//时间复杂度O(n),空间复杂度O(1)bool hasCycle(ListNode *head) {    if(head == NULL || head->next == NULL)        return true;    ListNode *slow = head;    ListNode *fast = head;    while(fast->next && fast->next->next)    {        slow = slow->next;        fast = fast->next->next;        if(slow == fast)            return true;    }    return false;}

暂时就总结了这三个方法，存在错误还希望大家指出。

转载地址：http://ihmmi.baihongyu.com/