**判断是否有环，通过判断是否能够产生节点的相交** ```python # Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: # 给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。 def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]: if not head: return None # 若有环 转一圈一定会再次回到环的起点 node_set = set() while head: if head in node_set: return head else: node_set.add( head ) head = head.next return None ``` --- **更加链表的做法：快慢指针** > **判断链表是否有环** 快慢指针法，分别定义 fast 和 slow 指针，从头节点出发，fast指针每次移动两个节点，slow指针每次移动一个节点，如果 fast 和 slow指针在途中相遇 ，说明这个链表有环。 因为fast是走两步，slow是走一步，相对于slow来说，fast是一个一个节点靠近slow，所以fast一定可以和slow相遇。 > **如何找到环的入口** 设： - 头节点到环形入口节点，距离设为x - 环形入口节点到fast指针和slow指针相遇节点，距离设为y - 相遇节点再到环形入口，距离设为z 所以相遇时，slow指针走过的节点数：x + y；fast指针走过的节点数：x + y + n * ( y + z )，n表示fast指针在环内走了n圈，才遇到slow。 **所以怎么确定环入口呢？** fast一次两个节点，slow一次一个节点， 所以 fast走过的节点数 = slow走过的节点数 * 2，即 (x + y) * 2 = x + y + n (y + z) 两边消掉一个（x+y）: x + y = n (y + z) 要找到环的入口，即确定x的值，将x单独放在左面：x = n (y + z) - y, 再从n(y+z)中提出一个 y+z 来，整理公式之后为如下公式：x = (n - 1) (y + z) + z 注意n一定是大于等于1的，因为fast至少要多走一圈才能相遇slow指针。 - 当n = 1，表示从头节点出发一个指针，从相遇节点也出发一个指针，这两个指针每次只走一个节点， 那么这两个指针相遇的时候就是环形入口的节点。 - 当n > 1，其实一样，只是多饶了(n-1)圈而已。 *这里需要好好想一下* > **为什么第一次在环中相遇，slow的 步数 是 x+y 而不是 x + 若干环的长度 + y ？** 核心结论：当 slow 刚进入环时，fast 已经在环中的某个位置。此时 fast 到 slow 的距离（沿着环的前进方向）一定小于环的长度。由于 fast 比 slow 快一步，在 slow 走完这一圈之前，fast 一定能追上。 ```python # Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]: if not head: return None fast = head slow = head while fast and fast.next: fast = fast.next.next slow = slow.next # 相遇点确定 if fast == slow: # 从头节点和相遇点分别出发步长为1的指针确定入环点 p = head q = slow while p != q: p = p.next q = q.next return p return None ```