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

旧城等待， 2022-11-28 13:27 168阅读 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 条评论，168人围观）

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

相关阅读

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

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

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

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

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

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

相关链表是否有环

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

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

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

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

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

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

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

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

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

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

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

相关判断链表是否有环

/ 判断链表是否有环快慢指针 / public class Test2 { public static void main(S

Love The Way You Lie/ 2022年10月29日 07:45/ 0 赞/ 191 阅读

相关有环链表

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

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

相关判断链表是否有环

给定一个单链表，只给出头指针h： 1、如何判断是否存在环？ 2、如何知道环的长度？ 3、如何找出环的连接点在哪里？ 4、带环链表的长度是多少？解法

素颜马尾好姑娘i/ 2022年03月25日 14:42/ 0 赞/ 294 阅读

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

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

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