056. 链表中环的入口结点

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

Solutions

　　其实这一个问题可以分解成三个子问题：

如何判断链表中是否包含环？
- 两个指针，一个走一步，一个走两步，如果有环俩指针必相遇。
如何确定环中节点的个数？
- 在 1 的基础上，从相遇点开始，一步一步走，边走边计数，回到当前结点时就走了一圈。
如何找到环的入口结点？
- 在 1 的基础上，假设慢的指针走了 $x$ 步，那么快的指针走了 $2x$ 步，而多走的部分都是在环上走的，下面细说。

　　基于上面的图，我们知道快指针慢指针多走了 x 步，多走的部分都是在环上走的，那么可以得到式子：

$2x - x = x = p(b+c)$

　　慢指针走过的步数有可以表示为：

$x=a + q(b+c) + b$

　　集合上面两个式子可得：

$p(b+c) = a + q(b+c) + b$ $a = (p-q)(b+c)-b = (p-q-1)(b+c)+c$

　　通过上面的式子我们知道，当从相遇点开始，我们重新找两个指针，一个在头节点位置，一个在相遇点，两个指针每次都走一步，这样的话肯定会在换入口处相遇。

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def EntryNodeOfLoop(self, pHead):
        # write code here
        pSlow = pHead.next
        if pSlow is None:
            return None
        pFast = pHead.next.next
        
        b_loop = False
        while pSlow is not None and pFast is not None:
            if pSlow == pFast:
                b_loop = True
                break
            pSlow = pSlow.next
            if pSlow is None:
                return None
            pFast = pFast.next.next
        
        if not b_loop:
            return None
        
        pRestart = pHead
        
        while True:
            if pRestart == pSlow:
                return pRestart
            pRestart = pRestart.next
            pSlow = pSlow.next
# 运行时间：32ms
# 占用内存：5844k

Solutions

References