牛客题霸 判断链表中是否有环 C++题解/答案

题目描述

判断给定的链表中是否有环
扩展：
你能给出空间复杂度的解法么？

题解：

在这介绍一个简便的方法：快慢指针
就是：一个指针走两步，一个指针走一步
快慢指针中，因为每一次移动后，快指针都会比慢指针多走一个节点，所以他们之间在进入环状链表后，不论相隔多少个节点，慢指针总会被快指针赶上并且重合，此时就可以判断必定有环。
如果快指针到达NULL，说明链表以NULL为结尾，没有环
为什么要这样？
如果两个指针只走一步，那就有可能完美错开，无法相遇，所以要造成速度差，使得能相遇
除了能找环，还可以用来找环入口，这里就不细讲了

代码：

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */
class Solution {
   
public:
    bool hasCycle(ListNode *head) {
   
        ListNode *l1=head;
        ListNode *l2=head;
        while((l1!=NULL)&&(l1->next!=NULL))
        {
   
            l2=l2->next;
            l1=l1->next->next;
            if(l2==l1)return 1;
        }
        return 0;
    }
};