链表----141. 环形链表

朱雀 2022-11-16 01:54 125阅读 0赞

【题目】给定一个链表，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。 否则，返回 false 。  
进阶：

你能用 O(1)（即，常量）内存解决此问题吗？  
![在这里插入图片描述][20210406070953336.png]  
输入：head = \[3,2,0,-4\], pos = 1  
输出：true  
解释：链表中有一个环，其尾部连接到第二个节点。  
【思路】快慢指针  
① 判断头节点与下一个节点不为空  
②快指针fast指向下一个节点， 满指针指向头节点  
③进入循环，循环条件（快慢指针不等），判断（快指针和下一个节点不为空），  
④慢指针走一个节点（next），快指针走两个节点（next.next）  
⑤快慢指针相等，跳出循环， 有环返回true  
【代码】

public class Solution {
        public boolean hasCycle(ListNode head) {
            if(head == null || head.next == null) {
                return false;
            }
            ListNode fast = head.next;
            ListNode slow = head;
            while (slow != fast){
    
                if(fast == null || fast.next == null){
                    return false;
                }
                slow = slow.next;
                fast = fast.next.next;
            }
            return true;
    
        }
    }

[20210406070953336.png]: /images/20221022/c0b4b7d3450a42329559c221ce3f5ca6.png

发表评论取消回复

表情：

评论列表（有 0 条评论，125人围观）

还没有评论，来说两句吧...

相关阅读

相关 141. 环形链表

题目来源 [leetcode][] 题目描述 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_

╰+哭是因爲堅強的太久メ/ 2023年02月10日 05:20/ 0 赞/ 77 阅读

相关链表----141. 环形链表

【题目】给定一个链表，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，我们使用整数 pos 来

朱雀/ 2022年11月16日 01:54/ 0 赞/ 126 阅读

相关 141. 环形链表

> 给定一个链表，判断链表中是否有环。 > > ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9

╰+哭是因爲堅強的太久メ/ 2022年10月07日 06:56/ 0 赞/ 119 阅读

相关 leetcode141环形链表

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

淡淡的烟草味﹌/ 2022年10月06日 08:53/ 0 赞/ 150 阅读

相关 141. 环形链表

[https://leetcode-cn.com/problems/linked-list-cycle/][https_leetcode-cn.com_problems_lin

系统管理员/ 2022年09月08日 00:21/ 0 赞/ 137 阅读

相关【LeetCode】141. 环形链表

题目链接：[https://leetcode-cn.com/problems/linked-list-cycle/description/][https_leetcode-cn

￡神魔★判官ぃ/ 2022年05月13日 14:26/ 0 赞/ 163 阅读

相关【leetcode】141. 环形链表

题目描述：给定一个链表，判断链表中是否有环。有返回True，无返回False。示例： > 有环示例： > ![20190226214956725.png][

「爱情、让人受尽委屈。」/ 2022年03月16日 06:56/ 0 赞/ 186 阅读

相关 leetcode:141. 环形链表

题目: 给定一个链表，判断链表中是否有环。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，

朱雀/ 2022年03月15日 03:52/ 0 赞/ 188 阅读

相关 leetcode 141. 环形链表

哈希 class Solution { public: bool hasCycle(ListNode head) {

ゞ浴缸里的玫瑰/ 2021年10月15日 00:17/ 0 赞/ 275 阅读

相关 leetcode【141】环形链表

给定一个链表，判断链表中是否有环。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没

灰太狼/ 2021年10月03日 01:44/ 0 赞/ 291 阅读