链表

环形链表 II

中等#142Java时间 O(n)空间 O(1)

题目要做什么

若链表存在环,返回环入口节点,否则返回 null。演示中的 pos 用来构造尾部连接,输出是入口节点的值。

题目示例输入head = [3,2,0,-4], pos = 1
题目示例输出2

01 为什么这样做

快慢指针先在环内相遇,再让 finder 从头节点出发,与 slow 同速前进。由相遇时的路程关系可得,两者会在入口相遇。

始终成立的条件

第二阶段,两指针距离入口的剩余路程模环长相同。

02 看见算法执行

动画与代码同步

修改输入,播放自己的例子

当前使用题目示例
修改输入会改变执行过程;预期输出用于核对结果。
数组 / nums步骤 1
执行状态
本次演示输出播放到最后查看

Solution.java参考解法
1class Solution {2    public ListNode detectCycle(ListNode head) {3        ListNode slow = head, fast = head;4        while (fast != null && fast.next != null) {5            slow = slow.next;6            fast = fast.next.next;7            if (slow == fast) {8                ListNode finder = head;9                while (finder != slow) {10                    finder = finder.next;11                    slow = slow.next;12                }13                return finder;14            }15        }16        return null;17    }18}

键盘控制:A 后退 · D 前进

编程练习

↑↓ 选择↵ 打开Pagefind 全文检索