快慢指针算法思想

快慢指针算法思想：

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 三个指针。