牛客题霸 判断链表中是否有环 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;
    }
};