长沙网站优化技巧,网站建设可行性分析表,wordpress怎么兼容浏览器,网站经常出现502代码随想录二刷 #xff5c; 链表 #xff5c;环形链表II 题目描述解题思路 代码实现判断链表是否有环如何找到环的入口 题目描述
142.环形链表II
给定一个链表的头节点 head #xff0c;返回链表开始入环的第一个节点。 如果链表无环#xff0c;则返回 null。
如… 代码随想录二刷 链表 环形链表II 题目描述解题思路 代码实现判断链表是否有环如何找到环的入口 题目描述
142.环形链表II
给定一个链表的头节点 head 返回链表开始入环的第一个节点。 如果链表无环则返回 null。
如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。如果 pos 是 -1则在该链表中没有环。注意pos 不作为参数进行传递仅仅是为了标识链表的实际情况。
不允许修改 链表。
示例 1
输入head [3,2,0,-4], pos 1 输出返回索引为 1 的链表节点 解释链表中有一个环其尾部连接到第二个节点。
示例 2
输入head [1,2], pos 0 输出返回索引为 0 的链表节点 解释链表中有一个环其尾部连接到第一个节点。
示例 3
输入head [1], pos -1 输出返回 null 解释链表中没有环。
提示
链表中节点的数目范围在范围 [0, 104] 内 -105 Node.val 105 pos 的值为 -1 或者链表中的一个有效索引
进阶你是否可以使用 O(1) 空间解决此题
解题思路 代码实现
本题主要解决两个问题
判断链表是否有环如果有环如何找到环的入口
判断链表是否有环
使用快慢指针法分别定义fast和slow两个指针从头节点出发fast指针每次移动两个节点slow指针每次移动一个节点如果两个指针在途中相遇说明这个链表有环。
强调途中的意思是指两个指针不是在链表末尾相遇的。
因为fast指针移动的快所以如果两个指针相遇一定是fast追上了slow指针并且一定是在环中相遇因为假如不在环中相遇fast是无法从slow的后面追上slow的。
至于fast为什么走两步slow为什么走一步是因为如果存在环fast相当于是一步一步的追赶slow也可以想象为slow没有动fast一次走一步这样就比较好理解了。
之所以slow也要移动是因为最终要找的是环的入口slow如果不移动环的入口就比较难判断。
如何找到环的入口
假设从头结点到环形入口节点的节点数为x。 环形入口节点到 fast指针与slow指针相遇节点节点数为y。 从相遇节点再到环形入口节点节点数为z。 如图所示 相遇时slow指针走过的路程为x yfast针走过的路程为x y n * (y z)n表示fast指针在环内走了 n 圈才遇到slow指针。
因为fast指针的速度是slow指针的两倍fast指针走的路程是slow指针走的路程的两倍
x y n * (y z) 2 * (x y)
因为要求的是环形入口节点的位置因此把 x 放在等式左边
x n * (y z) - y
再从其中提取出一个 y z来
x (n - 1) (y z) z
当 n 1时也就是fast指针只走了一圈时公式可化简为x z这表示如果从头节点出发一个指针从相遇节点也出发一个指针这两个指针每次只走一个节点 那么当这两个指针相遇的时候那个相遇的节点就是环形入口节点。
当n 1的时候由于y z就是环的长度这表示fast指针在圈内走了一些圈数最终还是能得出n 1时的结论。
class Solution{
public:ListNode* detectCycle(ListNode* head){ListNode* fast head;ListNode* slow head;while (fast ! NULL fast - next ! NULL) {slow slow - next; // slow移动一步fast fast - next - next; // fast移动两步if (slow fast) { // 当 fast 和 slow 相遇时ListNode* curA head;ListNode* curB fast;while (curA ! curB) {curA curA - next;curB curB - next;}return curA; // 找到入口节点}}return NULL:}
};
