跟着姚桑学算法-链表中环的入口结点

简介: 剑指offer算法

题.链表中环的入口结点

给定一个链表,若其中包含环,则输出环的入口节点。

若其中不包含环,则输出 null

数据范围
节点 val 值取值范围 [1,1000]。
链表长度 [0,500]。

样例
image.png

给定如上所示的链表:
[1, 2, 3, 4, 5, 6]
2
注意,这里的2表示编号是2的节点,节点编号从0开始。所以编号是2的节点就是val等于3的节点。

则输出环的入口节点3.
AI 代码解读

【题解】-- 链表,快慢指针扫描

用两个指针 first,second 分别从起点开始走,first 每次走一步,second每次走两步。
如果过程中 second 走到null,则说明不存在环。否则当 first 和 second 相遇后,让 first返回起点,second 待在原地不动,然后两个指针每次分别走一步,当相遇时,相遇点就是环的入口。
image.png

如上图所示,a 是起点,b 是环的入口,c 是两个指针的第一次相遇点,ab 之间的距离是 x,bc 之间的距离是 y。

则当 first 走到 b 时,由于 second 比 first 多走一倍的路,所以 second 已经从 b 开始在环上走了 x 步,可能多余1圈,距离 b 还差 y 步(这是因为第一次相遇点在 b 之后 y 步,我们让 first 退回 b 点,则 second 会退 2y 步,也就是距离 b 点还差 y 步);所以 second 从 b 点走 x+y 步即可回到 b 点,所以 second 从 c 点开始走,走 x 步即可恰好走到 b 点,同时让 first 从头开始走,走 x 步也恰好可以走到 b 点。所以第二次相遇点就是 b 点。

复杂度分析:

first 总共走了 2x+y 步,second 总共走了 2x+2y+x 步,所以两个指针总共走了 5x+3y步。
由于当第一次 first 走到 bb 点时,second 最多追一圈即可追上 first,所以 y 小于环的长度,
所以 x+y小于等于链表总长度。所以总时间复杂度是 O(n)。
AI 代码解读

C++代码实现:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *entryNodeOfLoop(ListNode *head) {
        if (!head || !head->next) return 0;
        ListNode *first = head, *second = head;

        while (first && second)
        {
            first = first->next;
            second = second->next;
            if (second) second = second->next;
            else return 0;

            if (first == second)
            {
                first = head;
                while (first != second)
                {
                    first = first->next;
                    second = second->next;
                }
                return first;
            }
        }

        return 0;
    }
};
AI 代码解读
目录
相关文章
C 408—《数据结构》算法题基础篇—链表(下)
408考研——《数据结构》算法题基础篇之链表(下)。
86 29
公司监控上网软件架构:基于 C++ 链表算法的数据关联机制探讨
在数字化办公时代,公司监控上网软件成为企业管理网络资源和保障信息安全的关键工具。本文深入剖析C++中的链表数据结构及其在该软件中的应用。链表通过节点存储网络访问记录,具备高效插入、删除操作及节省内存的优势,助力企业实时追踪员工上网行为,提升运营效率并降低安全风险。示例代码展示了如何用C++实现链表记录上网行为,并模拟发送至服务器。链表为公司监控上网软件提供了灵活高效的数据管理方式,但实际开发还需考虑安全性、隐私保护等多方面因素。
13 0
公司监控上网软件架构:基于 C++ 链表算法的数据关联机制探讨
C 408—《数据结构》算法题基础篇—链表(上)
408考研——《数据结构》算法题基础篇之链表(上)。
95 25
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构之单双链表按位、值查找;[前后]插入;删除指定节点;求表长、静态链表等代码及具体思路详解步骤;举例说明、注意点及常见报错问题所对应的解决方法
链表的中间结点
【10月更文挑战第24天】链表的中间结点是链表操作中的一个重要概念,通过快慢指针法等方法可以高效地找到它。中间结点在数据分割、平衡检测、算法应用等方面都有着重要的意义。在实际编程中,理解和掌握寻找中间结点的方法对于解决链表相关问题具有重要价值。
35 1
经典算法之链表篇(三)
经典算法之链表篇(三)
111 4
|
5月前
|
经典算法之链表篇(二)
经典算法之链表篇(二)
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等