题解
思路
[!hint]
题解
class Solution {
public ListNode detectCycle(ListNode head) {
ListNode fast, slow;
fast = slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) break;
}
// 上面的代码类似 hasCycle 函数
if (fast <mark> null || fast.next </mark> null) {
// fast 遇到空指针说明没有环
return null;
}
// 重新指向头结点
slow = head;
// 快慢指针同步前进，相交点就是环起点
while (slow != fast) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
}
// 详细解析参见：
// https://labuladong.online/algo/essential-technique/linked-list-skills-summary/
思路
[!hint]
- 环起点问题，首先想到相遇的地方大概率不会是起点
- 相遇的时候，慢指针走了 k 步，快指针走了 2k 步
- 假设当前相遇点距离环起点为 m 步，那么此时两个指针走相同步数（k-m）会再次相遇