LeetCode 141.环形链表

目录1 题目概述2 题目解法3 证明原题链接环形链表1 题目概述给你一个链表的头节点 head 判断链表中是否有环。如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。如果链表中存在环 则返回 true 。 否则返回 false 。示例1在遍历此链表时指针会在 2 到 -4 的这段区域不断地循环遍历因此链表中存在环示例2在遍历此链表时指针不会循环遍历链表最终会停止因此链表中不存在环2 题目解法在解决这道题目时所采用的方法是快慢指针法在使用快慢指针时保证慢指针每次走一步快指针每次走两步最终快慢指针相遇就能说明链表中存在环。如果快指针为空或快指针的下个结点为空则不存在环。存在环不存在环偶数个结点时奇数个结点时代码如下boolhasCycle(structListNode*head){structListNode*slowhead;structListNode*fasthead;while(fastfast-next){slowslow-next;fastfast-next-next;if(slowfast)returntrue;}returnfalse;}3 证明为什么慢指针走一步快指针走两步的话有环时它们一定能相遇呢如果慢指针走一步快指针走三步四步行不行呢首先来说说为什么慢指针走一步快指针走两步的话有环时它们一定能相遇以下面的链表为例在 slow 指针逐渐接近环时fast 指针已经在环内走了一段时间最终 slow 指针进入环时呈现出来的形式是这样的此时fast 和 slow 的距离为 4继续移动 slow 和 fast此时fast 和 slow 的距离为 3继续移动此时fast 和 slow 的距离为 2继续移动此时fast 和 slow 的距离为 1继续移动此时fast 和 slow 的距离为 0于是我们可以发现在快指针一次走两步慢指针一次走一步的情况下快慢指针之间的距离会逐渐缩小每次缩小1直到最后距离差为0因此我们可以假设在 slow 指针刚进环时fast 和 slow 之间的距离为 N在 fast 和 slow 逐渐移动的过程中距离 N 会不断减 1变成 N-1N-2N-3 … 1 0当距离为 0 时fast 和 slow 即可相遇因此在快指针一次走两步慢指针一次走一步的情况下两指针一定可以相遇再来说说如果慢指针走一步快指针走三步四步能不能让它们相遇在这里以慢指针走一步快指针走三步为例仍然假设在 slow 指针刚进环时fast 和 slow 之间的距离为 N此时如果让快慢指针开始移动那么快慢指针之间的距离差会逐渐减少 2变成 N-2N-4N-6N-8 …如果N 是偶数则距离最终会变成 0如果N 是奇数则距离最终会 变成 -1距离是 0表示 slow 和 fast 相遇距离是 -1表示 slow 和 fast 刚好错过无法相遇在这个情况下需要再次遍历环假设环的长度为 C那么fast 与 slow 的距离就是 C-1在遍历的过程中C-1又会不断地减2C-1 为偶数时最终会变成 0最终会相遇C-1 为奇数时最终会变成 -1最终不会相遇根据前面的结论如果一直不相遇那么 N 是奇数C是偶数真的是这样吗如果环内的结点较少环外的结点较多则在慢指针刚进环时快指针很有可能已经走了很多圈因此我们可以假设链表的起始位置到环的第一个结点的距离为 L快慢指针的距离为 N环的长度为 C此时slow 走过的距离为 Lfast 走过的距离为 L (x * C) (C - N) (x为走过的环的个数)又因为 fast 的速度为 slow 的三倍则距离也为 slow 的三倍因此可以得到等式 3L L (x * C) (C - N)化简可得 2L (x 1) * C - N根据我们得到的结论如果一直不相遇那么 N 是奇数C 是偶数将这个条件代入式中会发现并不成立因为偶数 ≠ 偶数 - 奇数在这样的情况下N 和 C 的取值只有下面两种情况N 为奇数C 为奇数N 为偶数C 为偶数当 N 为奇数C 为奇数时C - 1为偶数最终距离会为0快慢指针第一次不会相遇遍历第二次肯定会相遇当 N 为偶数时快慢指针一定会相遇所以slow 走一步fast走三步四步甚至更多时仍然会相遇