【编程刷题笔记】链表中环的入口结点

【编程刷题笔记】链表中环的入口结点

链表中环的入口结点

题目描述：题解代码

题目描述：

给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。
例如：
可以看到环的入口结点的结点值为3，所以返回结点值为3的结点。
牛客网题目链接

题解

这里用牛客上的一张图片写下官网解答的思路，不过我觉的官网的解释不太好，我重写一下自己关于这个思路的理解。

这里我们假设从头结点到环的入口结点的距离是x，从入口结点B到相遇点C的距离（只走一次的距离）为y，环的长度为N。

这里我们设置两个指针fast和slow，算法的步骤如下：
（1）fast和slow指针分别指向头结点
（2）fast指针每次移动两个结点，slow指针每次移动一个结点，当fast指针和slow指针相遇时，停止
（3）保持slow指针不动，fast指针指向头节点
（4）fast和slow指针每次移动一个结点，两个指针指向相同的结点时，这个结点就是入口结点。
证明如下。
在两个指针指向图一个结点C时，设slow指针此时绕环圈数为m，fast指针此时绕环圈数为n。则：
fast 指针走过的结点数为：x + y + n * N
slow 指针走过的节点数为: x + y + m * N
由于fast指针走过的结点数是slow的两倍，所以有：
x + y + n * N = 2 * （x + y + m * N）
化简上述结果可得：
x = (n - 2 * m) * N - y
由于n和m都是整数，所以(n - 2 * m)是整数，因此当fast指针和slow指针相遇和，fast从头结点开始，每次走一步，slow指针每次走一步，当fast走到结点B时，slow也恰好走到结点B，因此这个算法是正确的。

代码

def EntryNodeOfLoop(self, pHead):
  # write code here
   if pHead == None or pHead.next == None or pHead.next.next == None:
       return None

   fast = pHead.next.next
   slow = pHead.next
    
   while fast != slow and fast != None and fast.next != None:
       fast = fast.next.next
       slow = slow.next
   if fast == None or fast.next == None:
       return None
   fast = pHead
   while fast != slow:
       fast = fast.next
       slow = slow.next
   return fast