【腾讯】环形链表(证明有环)

旧城等待， 2022-11-28 13:27 180阅读 0赞

# 1. 题目描述 #

题目链接：[环形链表][Link 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70_pic_center]

# 2. 题目解析 #

1.  对于这种问题，最好的做法是~~~~做过一遍~ \_ ~
2.  简单来说，定义两个指针，一个快指针，一个慢指针，如果他们能够相遇的话，就代表该链表有环，否则如果快指针走到了null，则证明无环。
3.  这里说明下关于有环的证明：我们的快指针走2步，慢指针走1步，快指针会先在环里进行循环走，等到慢指针也走进环里时。**根据速度的相对，如果以满指针为参考系的话，快指针一次走一步，迟早会追上慢指针。**

# 3. 题目代码 #

public class Solution {
        
        public boolean hasCycle(ListNode head) {
        
           if(head == null){
        
               return false;
           }
           ListNode p1 = head;
           ListNode p2 = head;
           while(p2.next != null && p2.next.next != null){
        
               p1 = p1.next;
               p2 = p2.next.next;
               if(p1 == p2){
        
                   return true;
               }
           }
           return false;
        }
    }

[Link 1]: https://leetcode-cn.com/problems/linked-list-cycle/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70_pic_center]: /images/20221124/ca3ac7a1e2c14f8daa5ac364bf2b2c83.png

发表评论取消回复

表情：

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

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

相关阅读

相关 LeetCode题目之腾讯精选练习（50题）：环形链表 II

题目给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（...

阳光穿透心脏的1/2处/ 2024年04月19日 08:04/ 0 赞/ 83 阅读

相关 LeetCode题目之腾讯精选练习（50题）：环形链表

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

野性酷女/ 2024年04月18日 11:07/ 0 赞/ 89 阅读

相关算法-链表-环形链表（链表求环）

算法-链表-环形链表（链表求环） 1 题目出处 https://leetcode-cn.com/problems/linked-list-cycle-ii/ 2

迷南。/ 2023年07月24日 08:43/ 0 赞/ 53 阅读

相关单链表的相交以及有环无环问题（含数学证明）

单链表的有无环判断以及数学证明简介：单链表判断有环无环，在数据结构考研和在笔试面试题中都是链表问题的重难点。下面从拓扑关系，判断思路，数学证明，代码实现四个方面

浅浅的花香味﹌/ 2023年07月19日 10:43/ 0 赞/ 25 阅读

相关链表是否有环

链表是否有环 1、参考资料 https://leetcode-cn.com/problems/linked-list-cycle/ 2、题目要求 > 题目描

墨蓝/ 2022年12月03日 15:46/ 0 赞/ 183 阅读

相关【腾讯】环形链表(证明环的位置)

1. 题目描述题目链接：[环形链表II][II] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10

末蓝、/ 2022年11月28日 13:29/ 0 赞/ 164 阅读

相关【腾讯】环形链表(证明有环)

1. 题目描述题目链接：[环形链表][Link 1] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_

旧城等待，/ 2022年11月28日 13:27/ 0 赞/ 181 阅读

相关【腾讯精选练习 50 题】18—环形链表【简单】

题目链接 [141. 环形链表【简单】][141.] 题目简介给定一个链表，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪 `next` 指针再

冷不防/ 2022年11月19日 04:26/ 0 赞/ 258 阅读

相关有环链表

写在前面 > 剑指offer：链表中环的入口结点题目要求 > 给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。解法

系统管理员/ 2022年05月15日 21:49/ 0 赞/ 170 阅读

相关 leetcode 141. 环形链表（链表是否有环）

题目描述： ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly

缺乏、安全感/ 2022年02月26日 13:16/ 0 赞/ 304 阅读