链表

环形链表

简单#141Java时间 O(n)空间 O(1)

题目要做什么

判断链表是否存在环。演示输入 pos 表示尾节点连接到的下标,−1 表示没有环。pos 只用于构建输入,不是算法参数。

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

01 为什么这样做

慢指针每次走一步,快指针每次走两步。如果有环,快指针最终追上慢指针;如果快指针先到 null,则没有环。

始终成立的条件

存在环时,两指针在环内的相对距离每轮缩短一步。

02 看见算法执行

动画与代码同步

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

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

Solution.java参考解法
1class Solution {2    public boolean hasCycle(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) return true;8        }9        return false;10    }11}

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

编程练习

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