题目描述
给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。
题目地址
思路
第一步：判断是否存在环，用快慢指针，一个走一步，一个走两步，如果最终达到同一节点，则说明有环
第二步：寻找环的入口，假设入口结点距离头结点a个单位，fast和slow相遇在距离入口结点b个单位的位置，环剩下的长度为c，则有a+b+c+b = 2*(a+b) --> a = c 。因此，在重合时候，将fast置为head，再一步一步地走，当与slow重合时的结点即为入口结点。
Python
# -*- coding:utf-8 -*-
class ListNode:
def __init__(self,x):
self.val = x
self.next = None node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node4 = ListNode(4)
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node2 class Solution:
def EntryNodeOfLoop(self, pHead):
# write code here
if not pHead or not pHead.next:
return None
fast = slow = pHead
while fast and fast.next:
fast = fast.next.next
slow = slow.next
if slow == fast:
# 有环
fast = pHead
while fast != slow:
fast = fast.next
slow = slow.next
return fast
return None if __name__ == '__main__':
result = Solution().EntryNodeOfLoop(node1)