当前位置：首页 > article >正文

【C++】LeetCode：LCR 022. 环形链表 II

article 2024/12/4 15:44:24

题目：

给定一个链表，返回链表开始入环的第一个节点。从链表的头节点开始沿着 next 指针进入环的第一个节点为环的入口节点。如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。

说明：不允许修改给定的链表。

官方示例：

分析：

第一步，快慢指针判断是否有环，顺便找到相遇点位置；

第二步找到入环点；

第一步：

快慢指针遍历，相遇前是否能遍历到空，遍历到空指针就说明无环，相遇了就是有环（因为快指针从后面追上了慢指针。）

第二步：

主要是理解为什么代码中重定向了慢指针（重定向哪个指针不重要，主要是理解为什么a=c）

设链表起始点到入环点的距离为 a。

slow 指针进入环后，又走了 b 的距离与 fast 相遇。

相遇点到入环点的距离为c。

需要理解a=c,以下为推导。

设fast 指针已经走完了环的 n 圈，因此它走过的总距离为：

a+n(b+c)+b=a+(n+1)b+nc

因为快慢指针，fast 指针走过的距离都为 slow 指针的 2 倍。因此有:

a+(n+1)b+nc=2(a+b)

移项化简：

a=c+(n−1)(b+c)

因为b+c正好为环的一圈，

所以无论n为多少，都相当于快指针转了（n-1）圈又回到相遇点，即(n-1)(b+c)可以直接忽略

（说白了就是转一圈又回原地了，相当于没走）

所以： a=c

理解起始点到入环点和相遇点到入环点的距离相等后，就可以明白算法中重定向slow指针的原因是什么了。

// 找到环的入口
        slow = head;
        while (slow != fast) {
            slow = slow->next;
            fast = fast->next;
        }

重定向慢指针后，由于a=c，重定向后快慢指针每次都移动一格，正好可以在入环点相遇。

举例：

链表：[1,2,3,4,5,6,7,8,9], 入环点为3

（下面是我画的丑图）

分步：

初始状态：
- slow = 1，fast = 1。
第一次移动：
- slow = 2，fast = 3。
第二次移动：
- slow = 3，fast = 5。
第三次移动：
- slow = 4，fast = 7。
第四次移动：
- slow = 5，fast = 9。
第五次移动：
- slow = 6，fast = 4（fast 绕了一圈回到 4）。
第六次移动：
- slow = 7，fast = 6。
第七次移动：
- slow = 8，fast = 8（fast 再次绕了一圈，此时 slow 和 fast 相遇在节点 8）。

题解：

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if (!head || !head->next) return nullptr;

        ListNode *slow = head, *fast = head;
        bool hasCycle = false;

        // 检测是否存在环
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) {
                hasCycle = true;
                break;
            }
        }

        // 如果没有环，返回 nullptr
        if (!hasCycle) return nullptr;

        // 找到环的入口
        slow = head;
        while (slow != fast) {
            slow = slow->next;
            fast = fast->next;
        }

        return slow;  // 返回环的入口节点
    }
};