网站管理工作是具体应该怎么做,高校网站站群建设公司,t型网站域名和版面,湖南企业建站系统平台1141. 环形链表1 题目
1141. 环形链表
给你一个链表的头节点 head #xff0c;判断链表中是否有环。
如果链表中有某个节点#xff0c;可以通过连续跟踪 next 指针再次到达#xff0c;则链表中存在环。 为了表示给定链表…1141. 环形链表1 题目
1141. 环形链表
给你一个链表的头节点 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, 104]-105 Node.val 105pos 为 -1 或者链表中的一个 有效索引 。
进阶你能用 O(1)即常量内存解决此问题吗
2 我的想法
判断环的思想就是用一个追踪指针从头遍历到尾指针存在环的意思是如果在pos所指示的位置有追踪指针那么追踪指针和尾指针会交汇。
也就是说
1.如果有环尾指针指向pos所在节点
2.如果没有环第一种情况是单个元素第二种情况是尾指针一定不指向pos所在节点
/*** Definition for singly-linked list.* class ListNode {* int val;* ListNode next;* ListNode(int x) {* val x;* next null;* }* }*/
public class Solution {public boolean hasCycle(ListNode head) {}
}
难道写一个尾指针.next是否与pos节点一致的判断就好了吗
具体要怎么实现呢其实链表对应节点所在val值要是一样的呢我怎么表示pos节点我这样的想法可行吗如何写出合适的java代码如果是用遍历的话空间复杂度是O(1),时间复杂度是O(n)对吗写一个for循环加断
3 实现
关于你的想法的分析
你提到 写一个尾指针.next 是否与 pos 节点一致的判断这个思路存在几个问题
pos 不可用题目明确说明 pos 是系统内部使用的不会作为参数传递给我们的函数所以我们无法直接获取和使用 pos 值尾指针不存在在有环的链表中不存在传统意义上的 尾指针因为链表会循环没有终点val 值可能重复如你所担心的不同节点可能有相同的 val 值无法通过 val 来判断是否是同一个节点
所以我们需要一种不依赖 pos、不依赖节点值、且空间效率高的方法。
详细解题思路
最经典的解法是 快慢指针法也叫 龟兔赛跑算法思路如下 指针初始化 定义两个指针都从链表头部出发慢指针 (slow) 每次只移动 1 步快指针 (fast) 每次移动 2 步 核心逻辑 如果链表中没有环快指针会先到达链表末尾指向 null如果链表中有环两个指针最终一定会在环中相遇 因为快指针比慢指针移动得快进入环后会逐渐追上慢指针 终止条件 若快指针到达 null返回 false无环若快慢指针相遇返回 true有环
算法为什么有效
假设链表存在环当慢指针刚进入环时快指针已经在环内某个位置。此时可以看作快指针在追赶慢指针
快指针每次比慢指针多走 1 步相当于慢指针静止快指针以每秒 1 步的速度追赶只要在环内快指针最终一定会追上慢指针
/*** Definition for singly-linked list.* class ListNode {* int val;* ListNode next;* ListNode(int x) {* val x;* next null;* }* }*/
public class Solution {public boolean hasCycle(ListNode head) {// 处理边界情况空链表一定没有环if (head null) {return false;}// 初始化快慢指针ListNode slow head; // 慢指针每次走1步ListNode fast head.next; // 快指针每次走2步// 当快慢指针不相等时继续循环while (slow ! fast) {// 快指针到达末尾说明没有环// 注意要先判断fast是否为null再判断fast.nextif (fast null || fast.next null) {return false;}// 慢指针移动1步slow slow.next;// 快指针移动2步fast fast.next.next;}// 循环结束说明快慢指针相遇存在环return true;}
}复杂度分析 时间复杂度O (n)其中 n 是链表中的节点数 无环情况快指针会遍历 n/2 个节点就到达末尾有环情况最坏情况下两个指针在环中最多遍历 n 个节点就会相遇 空间复杂度O (1)只使用了两个指针不随链表长度变化满足题目进阶要求
其他可能的解法但不满足 O (1) 空间 哈希表法 遍历链表将每个节点存入哈希表每次访问节点前先检查哈希表如果已存在则有环空间复杂度 O (n)不满足进阶要求 标记法 遍历链表时给每个访问过的节点做标记如果遇到已标记的节点则有环需要修改节点结构实际中不常用
综上快慢指针法是解决这个问题的最优解既高效又节省空间。
4 两种解法
先回顾核心问题为什么判断链表有环不能靠 “节点值” 或 “pos”
在理解方法前先明确两个关键前提也是你之前担心的点
pos 是 “系统内部标记”我们拿不到题目里的 pos 只是用来给我们看 “环接在哪”实际写代码时函数参数只有head根本没有 pos 这个值所以没法用 “尾指针.next pos 节点” 这种思路。节点值可能重复不能作为判断依据比如链表是1→2→1→2有环两个 “1” 节点值相同但却是不同节点靠值判断会误判反之不同节点值也可能组成环所以 “值” 完全不可靠。
这也是为什么我们需要「哈希表」和「快慢指针」这两种不依赖 “值” 或 “pos” 的方法 —— 它们判断的是 “节点本身是否被重复访问”。
方法一哈希表法 ——“给走过的节点拍个照再遇到就是有环”
核心思路用 “哈希表” 当 “相册”记录所有走过的节点
就像你逛公园时每经过一个景点就拍张照存手机里。如果逛着逛着发现眼前的景点 “手机里早就有照片了”说明你绕回了之前的路有环如果一直走到公园出口链表末尾head null都没重复照片说明没环。
步骤拆解对应代码
我们用 Java 的HashSet哈希表的一种来实现 “相册”因为HashSet有个特性添加重复元素时会返回false这正好帮我们判断 “是否见过这个节点”。
public class Solution {public boolean hasCycle(ListNode head) {// 1. 初始化哈希表相册存的是“节点本身”不是节点值SetListNode seen new HashSetListNode();// 2. 遍历链表只要当前节点不为null没走到出口就继续走while (head ! null) {// 3. 尝试把当前节点加入哈希表// - 如果添加失败返回false说明之前见过这个节点→有环返回true// - 如果添加成功说明是第一次见继续往下走if (!seen.add(head)) {return true;}// 4. 移动到下一个节点逛下一个景点head head.next;}// 5. 走出循环说明head null走到出口没环返回falsereturn false;}
}关键细节为什么存 “ListNode” 而不是 “val”
存ListNode节点对象每个节点对象在内存中都有唯一的 “地址”哈希表判断重复时比较的是 “地址”能确保 “同一个节点才会被判定为重复”。存val节点值如之前说的值可能重复会导致 “不同节点被误判为重复”比如1→2→1无环第二个 “1” 会被误判为重复返回错误的true。
复杂度理解
时间复杂度 O (N)最坏情况是 “链表无环”我们要把所有 N 个节点都遍历一遍每个节点的 “添加” 和 “判断” 操作在哈希表中是 O (1)所以总时间是 O (N)。空间复杂度 O (N)最坏情况是 “链表无环”我们要把 N 个节点都存进哈希表所以空间是 O (N)—— 这也是它的缺点不如快慢指针省空间。
方法二快慢指针法Floyd 判圈算法——“让兔子和乌龟赛跑追上就是有环”
核心思路用两个速度不同的指针模拟 “兔子快” 和 “乌龟慢” 在链表上跑
如果链表没环兔子跑得比乌龟快会先跑到链表末尾fast null或fast.next null永远追不上乌龟。如果链表有环兔子会先进入环然后在环里绕圈等乌龟也进入环后兔子因为速度快总会在某个时刻追上乌龟两个指针指向同一个节点。
步骤拆解对应代码
先明确指针规则
慢指针乌龟每次走 1 步slow slow.next快指针兔子每次走 2 步fast fast.next.next
public class Solution {public boolean hasCycle(ListNode head) {// 1. 处理边界空链表headnull或只有1个节点head.nextnull肯定没环if (head null || head.next null) {return false;}// 2. 初始化指针慢指针从head出发快指针从head.next出发关键细节后面解释ListNode slow head;ListNode fast head.next;// 3. 循环只要快慢指针没相遇就继续跑while (slow ! fast) {// 4. 检查快指针是否到末尾如果fast或fast.next是null说明没环if (fast null || fast.next null) {return false;}// 5. 乌龟走1步兔子走2步slow slow.next;fast fast.next.next;}// 6. 跳出循环→快慢指针相遇说明有环返回truereturn true;}
}关键细节 1为什么初始时快指针要从head.next出发而不是和慢指针一起从head出发
这是为了适配while循环的 “先判断后执行” 逻辑
如果两个指针都从head出发初始时slow fastwhile (slow ! fast)的条件直接不满足循环不执行直接返回false—— 但此时如果链表有环比如head自己指向自己就会误判。快指针从head.next出发初始时slow headfast head.nextslow ! fast循环能正常开始即使链表是head自环head.next head第一次循环时 slow会走到head.next headfast会走到head.next.next head.next head此时slow fast跳出循环返回true判断正确。
如果想用 “两个指针都从head出发”可以把while改成do-while先执行后判断代码如下逻辑完全等价只是循环方式不同
public boolean hasCycle(ListNode head) {if (head null) return false;ListNode slow head, fast head;// do-while先移动再判断是否相遇do {// 快指针到末尾没环if (fast null || fast.next null) return false;slow slow.next;fast fast.next.next;} while (slow ! fast);// 相遇有环return true;
}关键细节 2为什么快指针走 2 步不是 3 步、4 步
核心是 “快指针速度比慢指针快”走 2 步是最简洁的选择
走 2 步时每次循环快慢指针的距离会减少 1比如初始距离 1下次距离 0初始距离 2下次距离 1再下次距离 0必然会相遇。走 3 步、4 步也能实现但代码会更复杂比如要多判断fast.next.next是否为 null且没有性能优势所以 2 步是最优选择。
复杂度理解
时间复杂度 O (N) 无环情况快指针走 N/2 步就到末尾因为每次走 2 步时间 O (N)。有环情况最坏是 “环很小乌龟进环前要走很多步”但总体来看快指针最多绕环 1 圈就能追上乌龟总步数还是 O (N)。 空间复杂度 O (1)只用到slow和fast两个指针不管链表多长都只占 2 个指针的空间完全符合题目 “O (1) 内存” 的进阶要求。
两种方法的对比怎么选
对比维度哈希表法快慢指针法核心逻辑记录已访问节点看是否重复速度差导致相遇时间复杂度O(N)O(N)空间复杂度O (N)需要存节点O (1)只需要两个指针代码简洁度较简洁依赖哈希表 API稍复杂需处理指针初始化适用场景除了判断环还想记录节点只需要判断环追求省空间
实际面试中快慢指针法是更优的选择—— 因为它满足 O (1) 空间也是面试官更想考察的思路能体现对链表特性的深入理解哈希表法更偏向 “直观思路”适合作为辅助理解的方法。
通过这两个方法的拆解你应该能彻底明白 “判断链表有环” 的核心逻辑了 下次遇到类似问题不管是用哈希表还是快慢指针都能清晰地写出代码啦
【解释if (!seen.add(head))】
我们来详细解释一下你看不懂的这行代码if (!seen.add(head))
这句话的作用
这句话的意思是尝试把当前节点head添加到哈希表seen中如果添加失败说明这个节点已经在哈希表中存在了就返回true表示有环
逐步拆解 seen是一个HashSetListNode类型的集合用来存储我们已经访问过的节点 seen.add(head)这个方法的特性 当我们往 HashSet 中添加元素时如果这个元素之前不存在就会添加成功返回true如果这个元素之前已经存在就会添加失败返回false !是逻辑非运算符用来取反 如果seen.add(head)返回true添加成功是新节点那么!true就是false不会进入 if 语句如果seen.add(head)返回false添加失败节点已存在那么!false就是true会进入 if 语句执行return true
举个生活化的例子
这就像我们去游乐园玩每个景点门口有个登记簿
第一次到某个景点我们在登记簿上写下名字添加成功继续游玩如果走到一个景点发现登记簿上已经有我们的名字了添加失败说明我们绕了一圈又回到了曾经去过的地方这就证明游乐园的路线是环形的
整个代码的逻辑流程
从头节点开始遍历链表每到一个节点就尝试把它加入哈希表如果添加失败节点已存在说明有环返回true如果添加成功就继续访问下一个节点直到遍历完所有节点head null说明没有环返回false
这样通过哈希表记录访问过的节点就能判断链表是否存在环了是不是很容易理解呢
