题目描述
给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。
思路
如果slow走了L的长度那么fast走了2L
假设从开始到入口点的长度是s，slow在环里走的长度是d
那么 l = s + d
假设环内slow没走的长度是m，fast走的长度是n*(m+d) + d + s = 2L
带入得n*(m+d) + d + s = 2（s+d） => s = m+(n-1)(m+d) m+d就是绕环一圈 所以s = m 所以相遇后，让slow和head一起走，相遇点就是入环节点
1
class
Solution:
2
def
EntryNodeOfLoop(self, pHead):
3
#
write code here
4
if pHead == None:
5return None
6 fastPointer = pHead
7 slowPointer = pHead
8while fastPointer and fastPointer.next:
9 slowPointer = slowPointer.next
10 fastPointer = fastPointer.next.next
11if fastPointer == slowPointer:
12break13if fastPointer == None or fastPointer.next == None:
14return None
15 fastPointer = pHead
16while fastPointer!=slowPointer:
17 fastPointer=fastPointer.next
18 slowPointer=slowPointer.next
19return fastPointer
2019-12-31 22:17:13
原文：https://www.cnblogs.com/NPC-assange/p/12127747.html
【说明】：本文章由站长整理发布，文章内容不代表本站观点，如文中有侵权行为，请与本站客服联系(QQ:254677821)！