快慢指针判断链表中是否有环_快慢指针判断链表是否有环

基本思想

快指针：从头开始移动 每次移动两个距离
慢指针：从头开始移动 每次移动一个距离

如果单链表中存在有环的话，那么快慢指针一定是会相遇的。

为什么？首先快指针在环内肯定是可以追上慢指针的对吧，那存不存在一种可能就是快指针恰好跳过了慢指针(因为快指针的步长为2)然后快慢指针就没有相遇了呢？答案是不存在这一种情况的，我们这里首先要明确一点就是“假如没有相遇，又何来的超越呢？”对吧，好比咱俩在操场上跑步，假如你都没有与我相遇那你又何谈超过我，对吧。

当快慢指针首次相遇的时候，慢指针肯定在环内的移动距离肯定没有超过一圈

为什么？假如慢指针在环内移动了第一圈，那在慢指针移动这一圈的过程中，快指针肯定是要超过慢指针的对吧？那么依据之前我们上一条所说的“有超越那就必然有相遇" 所以当快慢指针首次相遇的时候，慢指针的移动距离肯定是没有超过一圈的。

如何确定环的入口

假设单链表的头节点到环入口的距离为m，快慢指针在环内相遇的时候，慢指针在环内已经移动的距离为x，快指针已经移动了n圈，一个环有c个单位长度，那么可以列出一个等式那就是 2$\times$（m+x）=m+n$\times$c+x.从这个等式可以推出：m=n$\times$c-x。依据我们推出来的这个等式，我们就可以设置两个指针，一个指针指向头节点，一个指针指向快慢指针首次相遇的地方。然后两个指针每次移动一步，直到两个指针相等为止。此时两个指针所指向的地址就是单链表中环的入口的地址。

代码

//判断链表是否有环 如果有的话返回环入口
LNode* findLoopStart(LNode* list){
    //定义一个慢指针
    LNode* low = list;
    //定义一个快指针
    LNode* fast = list;
    //判断low->next 与 fast->next->next 是否相等
    while (low->next != NULL && fast != NULL && fast->next != NULL) 
    {
        //慢指针后移
        low = low->next;
        //快指针后移
        fast = fast->next->next;
        
        if (fast != NULL && low != NULL)
        {
            if (low->next == fast->next)
            {
                cout<<"该链表存在环"<<endl;
                break;
            }
        }
    }

    //fast/fast ->next/low->next == NULL 没有环
    if (fast == NULL ||fast->next == NULL || low->next == NULL)
    {
        cout<<"该单链表没有环"<<endl;
        return 0;
    }
    //返回环的入口点
    //指向快慢指针相遇时的节点
    LNode* meetPoint = low;
    //指向链表开头的节点
    LNode* head = list;
    //meetPoint = head
    while (meetPoint->data != head->data)
    {
        //相遇节点后移
        meetPoint = meetPoint->next;
        //开始节点后移
        head = head->next;
    }
    //返回环入口
    return head;
}
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
34
35
36
37
38
39
40
41
42
43
44
45
46

如何确定两个单链表是否有交叉

这里我们将其中一个链表的表尾指向另一个链表的表头，假如两个链表有交叉的话那么我们从任意两个链表的表头进行遍历最后肯定可以进入到环中，这里我们就可以用到上面的函数来判断首尾连接后的单链表是否有环.

参考资料

《2021年数据结构考研复习指导》 王道论坛