本文主要是介绍JZ23链表中环的入口结点，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
JZ23链表中环的入口结点
思路:
采用双指针，设定快指针fast_p是慢指针slow_p的2倍，如果有环，则当两指针第一次相遇时慢指针一定不可能在环中走超过一圈，因此假设头结点到环的开头距离为a,环开头到第一次相遇节点的距离为b，第一次相遇到环开头距离为c，因此快指针fast_p走过的距离=a + (b+c)k +b (k为大于1的正整数)，慢指针slow_p走过的距离= a + b 因为快指针走过的路程是慢指针的两倍，则有 (a+b)2 = a+(b+c)k+b 化简得 a = (k-1)(b+c) +c （k-1是大于0的整数）,此时让快指针从头和慢指针同样速度前进，两指针第一次相遇必在环的入口结点
如图：
代码如下：
class Solution:def EntryNodeOfLoop(self, pHead):# write code herefast_p = pHeadslow_p = pHeadwhile True:if slow_p == None:return slow_pfast_p = fast_p.next.nextslow_p = slow_p.nextif slow_p == fast_p:fast_p = pHeadwhile fast_p != slow_p:fast_p = fast_p.nextslow_p = slow_p.nextreturn fast_p
这篇关于JZ23链表中环的入口结点的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
