数据结构_找环，破环题-2.5

一. 判断单链表有无环

a. 错误的思路：遍历陷入死循环

1）和相交的遍历思路一样，找指向相同。

错误点

一直在死循环。

思考点：如何破环

b. 个人思路：反转链表回首结点

1）目前的经验，无非就是增删查改，反转链表，快慢指针，于是一个个靠；
2）发现，反转有环链表后，会回到首结点。
图解思路如图1:

图1 反转有环链表大体流程

增益点：反转破环

反转链表可以跳出环的死循环。

代码

typedef struct ListNode Node;
bool hasCycle(struct ListNode* head) {

    if (head == NULL)
        return false;

    Node* n1 = NULL;
    Node* n2 = head;
    Node* n3 = NULL;


    while (n2)
    {
        n3 = n2->next;
        n2->next = n1;

        n1 = n2;
        n2 = n3;
        if (n3)
            n3 = n3->next;
    }
    if (n1 == head && head->next != NULL) 回到首结点就是有环
        return true;

    return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

c. 参考思路：快慢指针转为追及问题

1）环相当于初中还是高中的一道物理题：在学校操场上，小狗速度是小猫的两倍，问小狗多久能追上小猫。即快指针为慢指针速度的两倍；
2）速度为两倍的考究点为，2-1=1，保证每次只追一个结点距离，实现追及结点遍历，避免陷入奇偶死循环的局面。

增益点：思路本身和二倍速度遍历所有结点

代码

typedef struct ListNode Node;
bool hasCycle(struct ListNode *head) {

    if(head==NULL||head->next==0)
    return false;

    Node* fast=head;
    Node* slow=head;
    Node* n3=NULL;


    while(fast)
    {
        fast=fast->next;
        if(fast)
        fast=fast->next;
        slow=slow->next;
        if(slow==fast)
        return true;
    }

    return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

二. 有环，返回入环结点地址

a. 个人思路一：继续反转链表找思路（缺陷就是无用遍历多了些）

1）发现在反转思路出环的状态会出现一个反向新环；
2）遍历反向新环得到入环结点地址。
图解思路如图2:
![在这里插入图片描述](https://img-blog.csdnimg.cn/direct/0fece3bbcb534614928f194064a0a681.png#pic_center

图2 反转过程形成的反向新环

图中，对应反转后的一次移位，利用这个反向新环的任意一结点store去遍历这个环，如果与n1地址相同，则n1为入环地址。

未解决的问题：编译器对的，oj不对

编译器结果如图3:

图3 编译器的监视窗口数据

从图中可以看出，store是找到了n1，并返回了n1的地址。

oj结果如图4:

图4 oj输出

输出是这没环？我编译器一步一步调试都是对的，还找到了入环结点，怎么到你这就找不到了？而且最开始思考的图解思路也是没错的。

代码

typedef struct ListNode Node;
struct ListNode* detectCycle(struct ListNode* head) {
    if (head == NULL)
        return NULL;

    Node* n1 = NULL;
    Node* n2 = head;
    Node* n3 = NULL;
    Node* store = NULL;

    while (n2)
    {
        n3 = n2->next;
        n2->next = n1;

        n1 = n2;
        n2 = n3;
        if (n3)
            n3 = n3->next;

        store = n1;
        while (store)     没环一定到NULL，有环就一直循环直到找到n1
        {
            store = store->next;
            if (store == n1)
                return n1;
           
        }
    }

    return NULL;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

b . 个人思路二：快慢指针公式求解，没做出来

列出未知数，如图5：

图5 快慢指针追及图

其中x为入环前跳数，y为慢指针入环后跳数，z为剩余跳数。

1）慢指针跑不了一个环，则x+y可知；
2）相遇后，再次跑一圈可以得到环的结点数：z+y+1。
3）快指针跳数：x+y+nz（n未知）;
4）慢指针跳数：x+y；
5）二倍速，中点数量关系：2*（x+y）=x+y+n*(y+z+1)。
四个未知数，三个等式，求不出来。

c . 参考思路一：未知数n无所谓

看成：
C=y+z+1;环结点数
2*（x+y）=x+y+nC;
x=C-y+(n-1)C;
可以看作，C-y是跑了(n-1)C的圈后的最后一圈位置。
(n-1)C相当于是白跑了(n-1)圈，不必知道n的具体大小。即从快慢指针相遇点出发一定能和head出发相遇

增益点：无，过于具体题目具体分析了

代码

typedef struct ListNode Node;
struct ListNode * detectCycle(struct ListNode *head) {


    if (head == NULL)
        return NULL;

    Node* slow = head;
    Node* fast = head;
    Node* store = NULL;
    while(fast)
    {
        fast=fast->next;
        if(fast)
         fast=fast->next;

        slow=slow->next;
        if(slow==fast)
        break;
    }
    if(fast!=slow)
    return NULL;

    store= slow;
    while(head!=store)
    {
        head=head->next;
        if(store)
        store=store->next;
    }
    return store;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

d . 参考思路二：我把环手动断开不就行了？还死循环？

1）快慢指针判断有无环；
2）有环，相遇点直接截断；
3）转换为两个链表求相交问题。移步至相交问题。

增益点：数学家思维

高中数学老师讲过数学家思维：
数学家知道烧水过程是把水倒进壶里，点火，烧水。
在面对一壶装满冷水的水时，
数学家会：把水倒掉--------》把水倒进壶里，点火，烧水。
正常人会：点火，烧水。