JZ23链表中环的入口结点

结点"/>

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