php 公司网站源码,三合一网站cms,wordpress文章摘要文字,网站建设责任分工表今天力扣刷到了一个特别有意思的题目#xff0c;于是就写了下面的题解来加深以下理解。
142. 环形链表 II - 力扣#xff08;LeetCode#xff09; 这个可以分为两大步去写#xff0c;首先要判断链表是否有环#xff0c;然后如果有环就去找到环的入口#xff0c;没有环返…今天力扣刷到了一个特别有意思的题目于是就写了下面的题解来加深以下理解。
142. 环形链表 II - 力扣LeetCode 这个可以分为两大步去写首先要判断链表是否有环然后如果有环就去找到环的入口没有环返回null。
判断链表是否有环
可以使用快慢指针法分别定义 fast 和 slow 指针从头结点出发fast指针每次移动两个节点slow指针每次移动一个节点如果 fast 和 slow指针在途中相遇 说明这个链表有环。
为什么fast 走两个节点slow走一个节点有环的话一定会在环内相遇呢而不是永远的错开呢
首先第一点fast指针一定先进入环中如果fast指针和slow指针相遇的话一定是在环中相遇这是毋庸置疑的。
那么来看一下为什么fast指针和slow指针一定会相遇呢
这是因为fast是走两步slow是走一步其实相对于slow来说fast是一个节点一个节点的靠近slow的所以fast一定可以和slow重合。
下面是我画的示例图帮助理解 如果有环寻找这个环的入口
此时已经可以判断链表是否有环了那么接下来要找这个环的入口了。
假设从头结点到环形入口节点 的节点数为x。 环形入口节点到 fast指针与slow指针相遇节点 节点数为y。 从相遇节点 再到环形入口节点节点数为 z。 如图所示 那么相遇时 slow指针走过的节点数为: x y fast指针走过的节点数x y n (y z)n为fast指针在环内走了n圈才遇到slow指针 yz为 一圈内节点的个数A。
因为fast指针是一步走两个节点slow指针一步走一个节点 所以 fast指针走过的节点数 slow指针走过的节点数 * 2
(x y) * 2 x y n (y z)
两边消掉一个xy: x y n (y z)
因为要找环形的入口那么要求的是x因为x表示 头结点到 环形入口节点的的距离。
所以要求x 将x单独放在左面x n (y z) - y ,
再从n(yz)中提出一个 yz来整理公式之后为如下公式x (n - 1) (y z) z 注意这里n一定是大于等于1的因为 fast指针至少要多走一圈才能相遇slow指针。
这个公式说明什么呢
先拿n为1的情况来举例意味着fast指针在环形里转了一圈之后就遇到了 slow指针了。
当 n为1的时候公式就化解为 x z
这就意味着从头结点出发一个指针从相遇节点 也出发一个指针这两个指针每次只走一个节点 那么当这两个指针相遇的时候就是 环形入口的节点。
也就是在相遇节点处定义一个指针index1在头结点处定一个指针index2。
让index1和index2同时移动每次移动一个节点 那么他们相遇的地方就是 环形入口的节点。
那么 n如果大于1是什么情况呢就是fast指针在环形转n圈之后才遇到 slow指针。
其实这种情况和n为1的时候 效果是一样的一样可以通过这个方法找到 环形的入口节点只不过index1 指针在环里 多转了(n-1)圈然后再遇到index2相遇点依然是环形的入口节点。
解答代码
代码如下
C:
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *detectCycle(ListNode *head) {ListNode* fast head;ListNode* slow head;while(fast ! NULL fast-next ! NULL) {slow slow-next;fast fast-next-next;// 快慢指针相遇此时从head 和 相遇点同时查找直至相遇if (slow fast) {ListNode* index1 fast;ListNode* index2 head;while (index1 ! index2) {index1 index1-next;index2 index2-next;}return index2; // 返回环的入口}}return NULL;}
};
java:
/*** Definition for singly-linked list.* class ListNode {* int val;* ListNode next;* ListNode(int x) {* val x;* next null;* }* }*/
public class Solution {public ListNode detectCycle(ListNode head) {ListNode slow head;ListNode fast head;while (fast ! null fast.next ! null) {slow slow.next;fast fast.next.next;if (slow fast) {// 有环ListNode index1 fast;ListNode index2 head;// 两个指针从头结点和相遇结点各走一步直到相遇相遇点即为环入口while (index1 ! index2) {index1 index1.next;index2 index2.next;}return index1;}}return null;}
}
