第 23 题：链表中环的入口结点
传送门：AcWing：链表中环的入口结点，牛客网 online judge 地址。
给定一个链表，若其中包含环，则输出环的入口节点。
若其中不包含环，则输出
null。样例：
image给定如上所示的链表：
[1, 2, 3, 4, 5, 6]，编号：2。
注意，这里的 2 表示编号是 2 的节点，节点编号从 0 开始。所以编号是 2 的节点就是 val 等于 3 的节点。则输出环的入口节点 3 。
分析：看的答案，记住结论就好，编码上还是要注意特判的情况，还有空指针的情况。“慢”指针进入环的时候，“快指针”要来追它，因为快慢指针走的步数差是固定的。例如： A 手上有 100 块钱，A 每天赚 10 块钱，B 手上有 50 块钱，B 每天赚 20，一定有一天，你们的钱相等，而且只要环内结点个数这么多就可以了。
image-20190110151143523
我写的错误解：
image-20190109132103035
Python 代码：
# 34. 链表中环的入口结点
# 给定一个链表，若其中包含环，则输出环的入口节点。
#
# 若其中不包含环，则输出null。
# Definition for singly-linked list.
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
class Solution(object):
def entryNodeOfLoop(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
# 先考虑边界情况
if head is None or head.next is None:
return None
slow = head
fast = head
while fast and fast.next:
# 慢指针走一步，快指针走两步
slow = slow.next
fast = fast.next.next
if slow == fast:
# 说明链表中存在环
break
# 注意：跳出循环的原因有两个，有可能是根本没有环，即上面 while fast and fast.next 不成立
# 也有可能是 slow == fast 里 break 的，分别讨论就可以了
if fast is None or fast.next is None:
return None
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
# 走到这里，说明 slow == fast
return slow
