本文主要是介绍剑指Offer(牛客网) 链表中环的入口结点,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目描述
给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出null。
来源:
https://www.nowcoder.com/practice/253d2c59ec3e4bc68da16833f79a38e4?tpId=13&tqId=11208&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tPage=3
我们设链表的无环的部分长度为L1,即有L1个节点,注意,这个L1是包括环的入口节点的。然后让环的长度是L2,这个L2也是包括环的入口节点。这个时候,p1和p2的交点如图所示,交点距离环的入口节点为a(从入口节点沿着行走方向走到交点),即在环的入口节点后面的第a个节点,就是交点,我用红色标记出a。
然后我们来考察一下L1,L2,a,以及n(n是走过的步数,不是走过的节点数,p1一步一个节点,p2一步两个节点)的关系。
忘记说一点了,我们可以明确的是,p1在进入环后,走了不到一圈就在交点处和p2重合,為什麼肯定没有走完一圈?因为p1在进入环的时候,p2和p1之间的距离(沿着行走方向)至多为 L2-1,不可能超过L2-1,因为环的大小也才只有L2 。p2追赶p1,最多只需要走L2-1步,因为每走一步,p1和p2的相对距离减小1,那么p1最多只走了L2-1步,就是最多只经过了L2-1个节点,不可能走完一圈。
现在可以列公式了:
L1+a=n #1 //n是p1走过的节点数
L1+kL2+a=2n #2 //2*n这个是p2走过的节点数,其中的k表示p2可能在环里面走了k圈,k>=1
由#2式减去#1式,有:
k*L2 = n #3
同时由#1和#3得到:
L1+a = k*L2 #4
接着由#4就得到了如下式:
L1 = k*L2 - a = (k-1)*L2 + (L-a)
得到这条式子就拨得云开见月明啊有木有,因为(L-a)表示的是交点与环入口的距离(从交点沿着行走方向到环入口),然后(k-1)是>=0的,因为p2在环中至少绕了一圈,这样我们就发现:L1的长度 = 环长度的整数倍 + 交点与环入口的距离
也就是说,p1再走L1步就可以达到环的入口。问题是L1不是已知的,没关系,在表头设置一个p3指针,p3每步前进一个节点。让p1和p3同时走,每次走1步,等p3和p1重合了,就是到了环口的位置了。Problem solved~
/*public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}
}
*/
public class Solution {public ListNode EntryNodeOfLoop(ListNode pHead){if(pHead==null||pHead.next==null)return null;ListNode fast = pHead;ListNode slow = pHead;while(fast!=null||slow!=null){fast = fast.next.next;slow = slow.next;if(fast==slow)break;//用快慢指针法证明有环则跳出}fast = pHead;//另用一个结点从起点跑起,在此与slow相遇的结点就是入口while(fast != slow){fast = fast.next;slow = slow.next;}return fast;}
}
这篇关于剑指Offer(牛客网) 链表中环的入口结点的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!