TUNIVERSE

142.环形链表Ⅱ

算法 链表 LeetCode
字数统计: 513阅读时长: 2 min
2022/07/27

快慢指针和万恶的数学推理

  • 快指针fast比慢指针slow多走两步，如果有环fast会追上slow，它们一定会相遇，同时它们相遇了说明在环内。此为第一次相遇。
  • 假设头结点到入环口有a个结点（不包括环的第一个结点），环的结点数为b。相遇时fast走的路程为2nb，slow走的路程为nb，n是fast比slow多走的圈数，证明过程如下。且慢指针再走a就能到达入环口，证明过程如下。
    1
    2
    3
    4
    5
    6
    7
    8
    //证明1
    1. 首先，fast走的路是slow路程的两倍，即f=2s；
    2. 其次，第一次相遇时fast比slow多走了n个环的路程，即f=s+nb;
    3. 联立上述两式，可解得：f=2nb，s=nb。

    //证明2
    1. 走到入环口的路程公式是：k=a+nb；
    2. 目前slow走了nb，再走a就能走到入环口。
  • 而head到入环口的距离刚好就是a，但是问题是a的值是未知的，所以需要用一个指针指向head（这里就用原来的快指针），一步一步地走来计数，同时慢指针也一步一步走，当它们相等时为第二次相遇，此时刚好走了a步。所以也就是说该指针具有如下性质：它和慢指针一起走a步后它们俩可以再入环口相遇

代码如下：

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
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {

        //慢指针cur，快指针nex，都指向第一个结点，重合
        //判断是否有环的变量hasCycle，初始为false
        ListNode *cur = head, *nex = head;
        bool hasCycle = false;

        //保证慢指针和快指针不为空
        while(nex!=NULL && nex->next!=NULL){
            cur = cur->next;
            nex = nex->next->next;
            //相等说明fast和slow相遇了，而它们必定在环内相遇，所以有环。
            if(nex == cur){
                hasCycle = true;
                break;
            }
        }

        //若有环
        if(hasCycle){
            //使nex指向第一个结点，固定cur，此时cur为
            nex = head;
            while(cur != nex){
                cur = cur->next;
                nex = nex->next;
            }
            return nex;
        }
        else    return NULL;
    }
};
CATALOG
  1. 1. 快慢指针和万恶的数学推理
Total : 68
2024
2023
2022
2021
2020
计算机视觉 三维重建 深度学习 动态规划 查找 教程 MongoDB 数据库 Neo4j MySQL 机器学习 GNN 随笔 故障诊断 Greenplum操作 Linux磁盘扩容 debug记录 环境问题 托福 多维索引 磁盘故障 列存分区 迁移学习 链表 LeetCode 双指针 剪枝 素数 逻辑题 并查集 树的遍历 字符串 数学模拟 完全二叉树 最短路径 哈希 排序 二叉搜索树 贪心 图论 图模拟 Set AVL树 DFS 栈 拓扑排序 递推 快乐模拟 图的遍历 前端 React Webpack Eslint top
华科课程 算法 学习笔记 年末总结 腾讯AI训练营 英语 database