判断单链表中是否有环？如果有起点在哪里？环长度？

柔光的暖阳◎ 2022-05-23 05:27 115阅读 0赞

#### 需求： ####

判断一个单链表是否有环？如果有换找出环的起点，以及环的长度。

#### 分析： ####

1）定义两个指针p1和p2，p1每次走1步，p2每次走两步，如果单链表有环则p1和p2一定会相遇；为什么一定有环一定会相遇？我们先定义一些变量：假设有环，环长为n，然后设 链表的起点 到 环起点 的长度为a，p1到环的起点时p2位于环的位置为x（0<=x<n）。

现在到这里就很容易的理解为什么一定会相遇，因为当p1到环的起点时，p2位于环的位置（距离环起点的顺时针位置）为x，那么p2与p1相差n-x步，而且p2每次总比p1块一步，所以一定会追上p1。

2）设p2和p1第一次相遇的点位于环的位（置距离环起点的顺时针位置）为b，此时

p1走的距离：a+b

p2走的距离：p2速度是p1的二倍所以 2\*(a+b)，但是因为p1和p2相遇所以p2走的距离也是 a+b+n\*k，即2\*(a+b) == a+b+n\*k，两边消去一个（a+b）

所以推导出 a+b == n\*k

3）如何找环的起点，第一次相遇之后，把指针p1拉回到链表的起点，然后把p2的速度改为每次走一步即和p1速度相同，p2把第一次相遇点作为起点，那么当p1和p2再次相遇的点就是圈的起点，因为第二次相遇时p1刚好走a步到环的起点，p2刚好走b+a步，由于b+a == n\*k刚好也在环的起点。

![20180603181405168][]

### 代码： ###

ListNode *detectCycle(ListNode *head) {
        ListNode *p1 = head, *p2 = head;
        do{
            if((p2 == 0) || (p2->next == 0)) {      //链表是有限长度的，已经走到链表尾部了，说明没有环
                return 0;
            }
    
            p2 = p2->next->next;         //p2一次走两步
            p1 = p1->next;//p1一次走一步
        }while(p1 != p2)
    
            for(p1 = head; p1 != p2; p1 = p1->next, p2 = p2->next);  //p1拉回起点，p2从相遇点开始走都是每次直走一步直到再次相遇p1就是起                                                                 //点
            return p1;
    }

###  ###

[20180603181405168]: /images/20220523/17af41c1f144469891453bd56ab15309.png

发表评论取消回复

表情：

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

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

相关阅读

相关 Java 判断单链表是否有环如果有环找到入口点

文章目录判断单链表是否有环如果有环找到入口点 1.判断单链表是否有环描述思路分析

痛定思痛。/ 2023年10月09日 13:45/ 0 赞/ 12 阅读

相关判断链表是否有环

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

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

相关判断链表是否有环

//判断链表是否有环 public static boolean IsLoop(Node head){ Node fast =

深碍√TFBOYSˉ_/ 2022年10月01日 05:50/ 0 赞/ 72 阅读

相关如何判断链表中是否有环

今天面试被问住了，很惭愧啊，回来上网查了一下思路。自己写了点程序。 1.如何判断是否有环？如果有两个头结点指针，一个走的快，一个走的慢，那么若干步以后，快的指针总会超过慢的指

谁借莪１个温暖的怀抱￠/ 2022年09月24日 05:17/ 0 赞/ 156 阅读

相关判断单链表中是否有环，找到环的入口节点

这类问题通常使用双指针的方法，即一个快指针一个慢指针。 faster = faster.next.next; slower = slower.next; “公理”：两指针

一时失言乱红尘/ 2022年05月24日 09:44/ 0 赞/ 158 阅读

相关判断单链表中是否有环？如果有起点在哪里？环长度？

需求：判断一个单链表是否有环？如果有换找出环的起点，以及环的长度。分析： 1）定义两个指针p1和p2，p1每次走1步，p2每次走两步，如果单链表有环则p1和p

柔光的暖阳◎/ 2022年05月23日 05:27/ 0 赞/ 116 阅读

相关判断链表是否有环

![这里写图片描述][70] //判断链表有环 public boolean hasCycle(ListNode head) {

忘是亡心i/ 2022年05月23日 04:42/ 0 赞/ 190 阅读

相关判断链表是否有环？

题目描述有一个单向链表，链表当中有可能出现“环”，就像下图这样。如何用程序判断出这个链表是有环链表？ ![70][] 方法一：首先从头节点开始，依次遍历单链表的每

你的名字/ 2022年05月14日 03:56/ 0 赞/ 214 阅读

相关判断链表是否有环

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

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

相关判断链表是否有环，有环则找到入口

设置两个指针p1,p2，p1每次走1步，p2每次走2步。当p2能与p1相遇，表明存在环。设p1走了S步，则p2走了2S步，又因为p2比p1多走了环的长度，即环的长度

你的名字/ 2021年09月26日 15:16/ 0 赞/ 320 阅读