【LeetHOT100】环形链表——Java多解法详解

一、题目描述141. 环形链表给你一个链表的头节点head判断链表中是否有环。如果链表中有某个节点可以通过连续跟踪next指针再次到达则链表中存在环。为了表示给定链表中的环评测系统内部使用整数pos来表示链表尾连接到链表中的位置索引从 0 开始。注意pos不作为参数进行传递仅仅是为了标识链表的实际情况。如果链表中存在环则返回true否则返回false。示例 1输入head [3,2,0,-4]pos 1输出true解释链表中有一个环其尾部连接到第二个节点。示例 2输入head [1,2]pos 0输出true解释链表中有一个环其尾部连接到第一个节点。示例 3输入head [1]pos -1输出false解释链表中没有环。提示链表中节点的数目范围是[0, 10⁴]-10⁵ Node.val 10⁵pos为-1或者链表中的一个有效索引进阶你能用 O(1)即常量内存解决此问题吗二、解题思路概览判断链表是否有环的核心问题是如何检测到某个节点被重复访问。解法时间复杂度空间复杂度特点哈希表法O(n)O(n)最直观易于理解快慢指针法Floyd判圈算法O(n)O(1)面试首选满足进阶要求三、解法一哈希表法最直观3.1 思路我们可以遍历链表使用一个HashSet来存储已经访问过的节点。每遍历到一个节点如果该节点已经存在于哈希表中说明链表有环否则将节点加入哈希表继续遍历。3.2 代码实现javapublic class Solution { public boolean hasCycle(ListNode head) { SetListNode set new HashSet(); ListNode p head; while (p ! null) { // 如果节点已经存在于集合中说明有环 if (set.contains(p)) { return true; } set.add(p); p p.next; } return false; } }3.3 复杂度分析时间复杂度O(n)遍历一次链表每次哈希表的插入和查找操作均为 O(1)。空间复杂度O(n)最坏情况下需要存储所有节点。3.4 优化写法利用Set.add()方法的返回值可以进一步简化代码javapublic class Solution { public boolean hasCycle(ListNode head) { SetListNode set new HashSet(); while (head ! null) { // add() 返回 false 表示元素已存在 if (!set.add(head)) { return true; } head head.next; } return false; } }四、解法二快慢指针法Floyd判圈算法4.1 思路这是面试中最高频的解法因为它满足O(n) 时间复杂度 O(1) 空间复杂度的进阶要求。核心思想定义两个指针——慢指针slow每次移动一步快指针fast每次移动两步。如果链表中有环快指针最终一定会追上慢指针如果链表无环快指针会先到达链表末尾null。可以把这个过程想象成两个人绕着环形跑道赛跑一个人跑得快一个人跑得慢如果是环形跑道跑得快的人总会追上跑得慢的人。4.2 代码实现javapublic class Solution { public boolean hasCycle(ListNode head) { if (head null || head.next null) { return false; } ListNode slow head; ListNode fast head; while (fast ! null fast.next ! null) { slow slow.next; // 慢指针走一步 fast fast.next.next; // 快指针走两步 if (slow fast) { // 相遇说明有环 return true; } } return false; // 快指针到末尾说明无环 } }4.3 另一种写法如果担心循环条件导致第一次循环时slow fast两者都指向head直接返回true可以将fast初始化为head.next并调整逻辑javapublic class Solution { public boolean hasCycle(ListNode head) { if (head null || head.next null) { return false; } ListNode slow head; ListNode fast head.next; while (slow ! fast) { if (fast null || fast.next null) { return false; } slow slow.next; fast fast.next.next; } return true; } }4.4 复杂度分析时间复杂度O(n)。当链表中不存在环时快指针遍历一遍链表即可结束当链表中存在环时在慢指针进入环后快指针最多需要一圈就能追上慢指针。空间复杂度O(1)只使用了两个指针变量。4.5 为什么快慢指针一定会相遇假设环的长度为b慢指针进入环时快指针距离慢指针的步数差为k0 k b。由于快指针比慢指针每次多走一步所以每走一步快指针与慢指针之间的距离就缩小 1。因此最多经过b步快指针就会追上慢指针。五、进阶题目142. 环形链表 II5.1 题目描述给定一个链表的头节点head返回链表开始入环的第一个节点。如果链表无环则返回null。说明不允许修改给定的链表。5.2 解法一哈希表法和 141 题类似遍历链表并将节点存入HashSet第一个重复出现的节点就是环的入口。javapublic class Solution { public ListNode detectCycle(ListNode head) { SetListNode set new HashSet(); ListNode p head; while (p ! null) { if (set.contains(p)) { return p; // 重复节点即环的入口 } set.add(p); p p.next; } return null; } }时间复杂度O(n)空间复杂度O(n)5.3 解法二快慢指针法Floyd判圈算法⭐数学推导这是本题的标准解法空间复杂度为 O(1)。首先需要理解几个变量x从头节点到环入口的节点数y从环入口到第一次相遇节点的节点数z从第一次相遇节点到环入口的节点数即剩余环的长度当快慢指针相遇时慢指针走过的路程x y快指针走过的路程x y n(yz)其中n表示快指针在环内绕的圈数因为快指针速度是慢指针的两倍2(x y) x y n(yz)整理得x n(yz) - y (n-1)(yz) z这个等式的数学含义是从头节点出发走x步到达环入口从相遇点出发走(n-1)(yz) z步也到达环入口。因此我们可以先用快慢指针找到第一次相遇点将其中一个指针放回头节点两个指针以相同的速度每次一步前进再次相遇的节点就是环的入口代码实现javapublic class Solution { public ListNode detectCycle(ListNode head) { if (head null || head.next null) { return null; } ListNode slow head; ListNode fast head; // 1. 判断是否有环并找到第一次相遇点 while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; if (slow fast) { // 2. 找到环入口 ListNode ptr head; while (ptr ! slow) { ptr ptr.next; slow slow.next; } return ptr; } } return null; } }图解示例以链表[3,2,0,-4]且pos1为例text链表结构 3 → 2 → 0 → -4 ↑__________↓x 13 → 2 经过1步到达环入口节点2快慢指针在某个环内节点相遇后将ptr指向头节点3ptr和slow同步前进最终在环入口节点2处相遇复杂度分析时间复杂度O(n)空间复杂度O(1)5.4 常见误区指针初始化的细微差别有些实现会将fast初始化为head.next这会导致相遇点的位置有所不同但数学推导依然成立最终都能正确找到环入口。关键是理解x (n-1)(yz) z这个等式的核心思想。六、解法对比与总结题目解法时间复杂度空间复杂度适用场景141. 环形链表判断是否有环哈希表O(n)O(n)快速实现无空间限制141. 环形链表判断是否有环快慢指针O(n)O(1)面试首选满足进阶要求142. 环形链表 II找环入口哈希表O(n)O(n)简单直接142. 环形链表 II找环入口快慢指针O(n)O(1)标准解法数学推导精妙6.1 面试建议在面试中建议优先使用快慢指针法对于 141 题直接使用快慢指针判断相遇即可对于 142 题先用快慢指针找到相遇点再利用数学推导找到环入口核心要点注意边界条件空链表或单节点链表直接处理理解快慢指针相遇的数学原理142 题的数学推导是考察重点建议理解并能复述七、相关链接141. 环形链表LeetCode 题目链接141. 官方题解环形链表官方题解142. 环形链表 IILeetCode 题目链接142. 官方题解环形链表 II 官方题解