快慢指针算法

快慢指针算法思想：

1. 定义快慢指针 fast 和 slow，起始均位于链表头部。规定 fast 每次后移 2 步，slow 后移 1 步；

2. 若 fast 遇到 null 节点，则表示链表无环，结束；

3. 若链中有环，fast 和 slow 一定会再次相遇；

4. 当 fast 和 slow 相遇时，额外创建指针 ptr，并指向链表头部，且每次后移 1 步，最终 slow 和 ptr 会在入环点相遇。

142. 环形链表 II - 力扣（LeetCode）

public class Solution {     public ListNode detectCycle(ListNode head) {         if (head == null) {             return null;         }         ListNode slow = head, fast = head;         while (fast != null) {             slow = slow.next;             if (fast.next != null) {                 fast = fast.next.next;             } else {                 return null;             }             if (fast == slow) {                 ListNode ptr = head;                 while (ptr != slow) {                     ptr = ptr.next;                     slow = slow.next;                 }                 return ptr;             }         }         return null;     } }

为什么 fast 指针每次移动 2 步，能不能移动 3、4、5...步？

设环外长度为 w，环长度为 s。取一特殊值 j，保证 j>w 且是 s 整数倍的最小值。将 slow 走了 j 步后的位置记为 X(j)，则 fast 走了 kj 步，记为 X(kj)，其中 k 为 fast 与 slow 的速度比值。

因为 j>w，所以 slow 和 fast 都在环内，而且 X(kj)可以看做从 X(j)出发，走了(k-1)*j 步，因为 j 是环长的整数倍，所以又回到了 X(j)，两者相遇。

从上面的分析可知，无论 fast 取任何值，两者都会相遇。即使比值 K 是小数 2.3（如 slow=10，fast=23），也只需要 j 乘以 10，就证明了这个问题。

我们之所以取 fast=2，是因为快指针的时间复杂度为 O(n*fast)，可以保证算法效率最高。

• 时间复杂度：O(N)，N 为链表节点数量，通过问题 2、问题 3 的解答，slow 与 fast 相遇时，slow 不会绕环超过一周；寻找入环点时，也只走了环外距离 a。因此，总的执行时间为：

• 空间复杂度：O(1)。因为只使用了 slow、fast、ptr 三个指针。