环形链表问题（判环+寻找入环点）_判断链表是否有环c++ 快慢指针

这篇文章，我们来看两道环形链表相关的题目。

题目1.判断链表中是否有环

链接: link

给你一个链表的头节点 head ，判断链表中是否有环。如果链表中存在环 ，则返回 true 。 否则，返回 false 。

1.1 思路分析（快慢指针）

什么是环形链表呢？

其实就是链表的尾结点的next不指向NULL，而是指向链表中的任意一个结点，也可以是自己。

我们来简化一下环形链表的图，其实就是长这样：

那这道题单纯的要判断链表中是否存在环其实很简单，思路就可以用我们熟悉的快慢指针：

定义两个指针fast和slow，初始都指向链表的第一个结点。然后快指针fast一次走两步，慢指针slow一次走一步。
如果链表中存在环，那他们就一定会相遇，即fast==slow。
如果链表中没有环，那么fast指针一定会率先走到空，因为fast是一次走两步，所以要考虑链表的可能是奇数个也可能是偶数个。
如果是奇数个循环结束条件是fast->next＝＝NULL
偶数个的话就是fast==NULL时结束

那我们来写一下代码：

就过啦！

bool hasCycle(struct ListNode *head) {
    struct ListNode* slow,*fast;
    fast=slow=head;
    while(fast&&fast->next)
    {
        fast=fast->next->next;
        slow=slow->next;
        if(slow==fast)
            return true;
    }
    return false;
}
1
2
3
4
5
6
7
8
9
10
11
12

代码呢确实很简单，但是，还有一些问题值得我们来思考一下

1.2 思考：为什么快指针每次走两步，慢指针每次走一步两者一定可以相遇？

大家有没有想过为什么快指针每次走两步，慢指针每次走一步在带环的情况下两者一定可以相遇呢？

我们来一起证明一下：

慢指针slow一次走一步，我们假设慢指针进环的时候，fast和slow的距离是N

那此时fast和slow两个人都在环里，两者距离为N，而fast又比slow走得快，所以fast是不是就有可能追上slow。

那为什么fast一次走两步，slow一次走一步就一定可以追上呢？两者就一定会相遇呢？有没有可能会错过呢？

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/一键难忘520/article/detail/895281