题目描述
给一个链表，若其中包含环，请找出该链表的环的入口节点，否则，输出null。

# -*- coding: utf-8 -*-# @Time : 2019-04-23 22:40# @Author : Jayce Wong# @ProjectName : job# @FileName : entryNodeOfLoop.py# @Blog : https://blog.51cto.com/jayce1111# @Github : https://github.com/SysuJayceclass ListNode: def __init__(self, x): self.val = x self.next = Noneclass Solution: def EntryNodeOfLoop(self, pHead): if not pHead: return None """ 首先使用快慢指针来判断是否有环：初始时快指针和慢指针都指向head，然后快指针每次走2步， 慢指针每次走1步，如果有环，那么在快指针走完2步之后一定会相遇。证明如下： 情况1：相遇前快指针落后慢指针1步，那么再走一次之后快慢指针相遇 情况2：相遇前快指针落后慢指针2步，那么再走一次之后快指针落后慢指针1步，回到情况1 情况3：相遇前快指针落后慢指针n步，那么再走一次之后快指针落后慢指针n-1步，经过n-1次之后 回到情况1 因此，如果链表存在环，那么在快指针走完2步、慢指针走完1步之后一定会相遇，不存在快指针走1步 之后相遇的可能 """ fast = slow = pHead hasLoop = False while fast.next: fast = fast.next slow = slow.next if fast.next: fast = fast.next if fast == slow: hasLoop = True break if not hasLoop: return None """ 如果存在环，那么在第一次快慢指针相遇的时候将快指针指向head，然后快指针和慢指针一起以每次 走1步的速度移动，当第二次相遇的时候就是环的入口。证明如下： 假设第一次相遇的时候慢指针走了N步，那么快指针就走了2N步。如果慢指针继续走N步那么就会回到 第一次相遇的位置，而此时让快指针从head开始走N步也会到达第一次相遇的位置。 既然会同时到达第一次相遇的位置，那么快指针和慢指针在回到第一次相遇的位置之前会有一段共同 的路，由于慢指针现在只走在环里，说明共同的路出现在环里，而快慢指针的第二次运动的起点不一样 因此在快指针到达环的入口的时候慢指针一定也在环的入口，之后两指针保持相同速度继续想第一次 相遇的位置移动。 所以，如果存在环，那么将快指针(或者另外设一个指针)指向head，然后和慢指针一起一次走1步。 他们再次相遇的位置就是环的入口(因此此后需要同步移动到第一次相遇的位置)。 """ fast = pHead while fast != slow: slow = slow.next fast = fast.next return fast