题目

如果一个链表中包含环，如何找出环的入口节点？

思路

  1. 确定是否包含环；
  2. 找到环中节点的数目；
  3. 找到环的入口。

1. 确定是否包含环

快慢指针。快指针一次走两步，慢指针一次走一步。
如果快指针追上慢指针，则有环；
如果快指针走到链表末尾（指向None)没有追到慢指针，则没有环。

2.找打环中节点的数目

快指针追上慢指针，相遇的节点在环中。
从这个节点出发，边移动边计数，再次回到这个节点，就得到环中节点数。

3. 找到环入口

快慢指针。参考倒数第k个节点。假设环中有n个节点，快指针先移动n步，慢指针再开始。随后同样速度移动，当慢指针指向倒数第n个节点，快指针刚好环入口。

https://leetcode-cn.com/problems/linked-list-cycle-ii/

代码

  1. # Definition for singly-linked list.
  2. # class ListNode:
  3. #     def __init__(self, x):
  4. #         self.val = x
  5. #         self.next = None
  7. class Solution:
  8.     def detectCycle(self, head: ListNode) -> ListNode:
  9.         # 首先初始化快指针和慢指针，确保快指针走的路的长度是慢指针长度的2倍
  10.         if head and head.next:
  11.             fast = head.next.next
  12.             slow = head.next
  13.         else:
  14.             return None  # 说明无环
  16.         # 进行循环，首先让快指针和慢指针第一次相遇
  17.         while fast:
  18.             if fast != slow:
  20.                 # 快指针走两步
  21.                 if fast.next:
  22.                     fast = fast.next.next
  23.                 else:
  24.                     return None  # 说明无环
  26.                 # 慢指针走一步
  27.                 slow = slow.next
  28.             else:
  29.                 detection = head
  30.                 while detection != slow:  # 此时由于slow和fast是一样的，用哪个都行
  31.                     slow = slow.next
  32.                     detection = detection.next
  34.                 return detection