题目描述

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

示例 1：

img

1
2
3
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

具体见题目详解。

算法思路

最近很久没做题了，因为才开学老是摆烂……这道题目我想的很简单，就是遍历链表，同时存储节点，如果当前节点已经存在于“记录”中，那么这个节点就是入口，因此代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        // set<ListNode *>
        set <ListNode*> myset;
        ListNode * tmp;
        tmp = head;
        int last_size = 0;
        while(tmp != nullptr) {
            myset.insert(tmp);
            if (myset.size() == last_size) {
                // 此时tmp即为链表环形入口
                return tmp;
            }
            last_size ++;
            tmp = tmp->next;
        }
        return nullptr;
    }
};

但是题目要求使用 O(1)的空间复杂度，很显然上面是达不到的，因此我只能查看题解，发现一个比较有启发的思路，先看代码：

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (fast == slow) {
                //在环上遇到
                while(slow!=head){
                    //slow走c步，head走c步，slow就可以到达环的入口
                    slow=slow->next;
                    head=head->next;
                }
                return slow;
            }
        }
        return nullptr;

    }
};

打眼一看就是快慢指针的运用，但是一般来说，快慢指针不是用来寻找链表中点的吗？在这里有什么用呢？具体解释涉及到数学原理，我直接引用GPT的回答：

这个代码利用了著名的弗洛伊德（Floyd）的快慢指针算法，也叫龟兔赛跑算法。下面详细解释其原理：

1. 检测环的存在

  • 快慢指针：
    • 定义两个指针：slow 每次走一步，fast 每次走两步。
    • 如果链表存在环，两个指针最终必然会在环内相遇；如果不存在环，则 fast 或 fast->next 会变为 NULL，退出循环返回 NULL。

2. 确定相遇后找入口

  • 当 slow 与 fast 相遇时（说明链表中存在环），此时相遇点在环内，但不一定是环的入口。
  • 然后，代码中设立两个新指针：
    • index1 从相遇点出发，
    • index2 从链表的头部出发。
  • 两个指针都每次走一步，最终它们相遇的节点正好是环的入口。

3. 为什么这样能找到环的入口？

  • 数学证明：
    假设：

    • 从链表头到环入口的距离为 d，
    • 环入口到相遇点的距离为 p，
    • 环的长度为 L，
    • 当 slow 指针走到相遇点时，走过的总距离为 d + p，
    • 此时 fast 指针走过的距离为 d + p + nL（因为 fast 在环内多走了若干圈，记作 n 圈）。

    由于 fast 的速度是 slow 的两倍，所以有：

    化简得：

    这意味着从相遇点沿环走 nL - p（实际上等价于走 d）步后就能到达环的入口。因此：

    • 当一个指针从头开始走 d 步，另一个指针从相遇点开始走 d 步，它们会在环入口处相遇。

这里的重点就在于理解d = nL-p这一步，我们可以想到，当前停留在相遇节点的指针，其距离入口就是p，其经过nL步后还是回到了原位，再剪掉一个p，就相当于回到了入口，此时另一个指针走了d步，也刚好在入口。