共计 627 个字符,预计需要花费 2 分钟才能阅读完成。
首先须要应用 Floyd 判圈算法(又称龟兔赛跑算法)的快慢指针思维找到环内快慢指针相遇点 c。
如图所示:
假如终点为 a,环的入口点为 b。终点 a 到环入口点的间隔为 x,环的入口点到快慢指针相遇点间隔为 y。
从快慢指针相遇点将 慢指针往回倒退 y 步 达到点 b,因为快指针速度是慢指针的两倍,故快指针会倒退到 c ’ 点,其中 b 到 c ’ 的间隔也为 y。即当慢指针走到 b 点时,快指针的地位在 c ’。因为慢指针此时走了 x 步,故快指针从 a 走 2x 步达到了 c ’ 点。进而等价于 快指针从 b 点走 x 间隔会走到 c ’ 点。
因为 bc = bc’,故 从 c 点走 x 间隔会走到 b 点。a->b == c->b[当然 c 到 b 可能走了不止一圈]。
综上,当快慢指针相遇后,设置两指针 p1、p2,p1 终点为 a,p2 终点为 c,同时一走一步,当 p1 和 p2 相遇,即为环的入口点。p1、p2 可重用快慢指针。
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) break;
}
if (fast == null || fast.next == null) return null;
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
正文完
发表至: leetcode算法
2022-02-08