当前位置：首页 > news >正文

面试官问我‘龟兔赛跑’怎么找链表环起点，我用Floyd算法5分钟讲清楚了

news 2026/6/6 16:22:50

面试官问我‘龟兔赛跑’怎么找链表环起点，我用Floyd算法5分钟讲清楚了

"链表环检测"是技术面试中的高频考点，而真正能让面试官眼前一亮的，往往不是背诵代码的能力，而是对算法原理的透彻理解。最近一次大厂面试中，当面试官抛出这个经典问题时，我选择用Floyd判圈算法配合物理直觉进行推导，最终不仅顺利解题，还获得了"解释清晰"的评价。本文将还原这次解题思路，带你掌握如何像数学家一样思考链表环问题。

1. 从龟兔赛跑到快慢指针：算法思想拆解

想象操场上有两位速度不同的跑步者：兔子（快指针）每次移动两步，乌龟（慢指针）每次移动一步。当跑道呈环形时，无论环有多大，快者终将追上慢者——这个生活常识正是Floyd算法的核心隐喻。

数学本质可以表述为：

设链表非环部分长度为L，环长度为C
慢指针进入环时，快指针已在环内移动L % C的位置
由于快指针相对慢指针速度为1（2步-1步），相当于每单位时间缩短1个节点距离
最大追赶时间不超过环长C，故时间复杂度为O(L + C)

// 基础检测代码框架 public boolean hasCycle(ListNode head) { ListNode slow = head, fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) return true; } return false; }

关键理解：快指针速度必须是慢指针的整数倍（通常取2倍），这样才能保证在有限步骤内相遇。若取非整数倍速度，可能陷入无限追逐。

2. 环起点定位的数学推导：相遇点与起点的神奇联系

当快慢指针首次相遇后，重置慢指针到链表起点，然后两者同速前进，再次相遇点即为环的入口。这个看似魔术般的结论，其实可以通过严格的数学推导验证：

设第一次相遇时：
- 慢指针移动距离：S = L + N*C + D
- 快指针移动距离：2S = L + M*C + D
- 其中N、M为整圈数，D为环内相遇点与入口距离
两式相减得：
```
S = (M-N)*C => L + D = K*C (K为整数)
```
这意味着从起点到入口的距离L，等于K*C - D——正好是从相遇点绕环K-1圈再后退D步的位置。

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

3. 空间复杂度对比：为什么Floyd优于哈希表？

常见解法是使用哈希表存储访问过的节点，但Floyd算法的优势在于其常数级的空间复杂度：

方法	时间复杂度	空间复杂度	适用场景
哈希表法	O(n)	O(n)	通用但耗内存
Floyd算法	O(n)	O(1)	内存敏感场景
标记法	O(n)	O(1)	允许修改链表时使用

实际面试中，面试官往往会追问："如果链表特别长（比如上百万节点），哪种方法更合适？"——这时Floyd算法的空间优势就显现出来了。

4. 边界条件与工程实践中的陷阱

看似简单的算法在实际编码时却暗藏多个"坑点"，这也是面试官考察的重点：

空指针处理：

// 必须优先检查fast.next非空 while (fast != null && fast.next != null)

初始条件设定：
- 错误做法：快慢指针初始位置不同步
- 正确方式：都从head开始
循环终止条件：
- 仅检查fast非空可能引发NPE
- 需要同时检查fast和fast.next

环长度计算技巧：

int cycleLength = 0; do { slow = slow.next; cycleLength++; } while (slow != fast);

5. 从算法到现实：Floyd的延伸应用

这个算法不仅适用于链表检测，还能解决许多有趣的数学问题：

快乐数判定（LeetCode 202）：

def isHappy(n): def next_num(x): return sum(int(d)**2 for d in str(x)) slow = fast = n while True: slow = next_num(slow) fast = next_num(next_num(fast)) if fast == 1: return True if slow == fast: return False