链表中环的入口节点

链表中环的入口节点

https://leetcode-cn.com/problems/c32eOV/

这里介绍双指针做法

image-20210928200135742

1. 判断链表是否存在环

这里使用最经典的快慢指针解法，两个指针同时前进，慢指针一次走一步，快指针一次走两步，若链表存在环，则二者一定会有相遇的机会。若不存在环，则由于快指针走的比较快则会先到达空指针。

2. 存在环，找入口点

假设在步骤1中快慢指针相遇，即存在环，并且在环中顺时针移动。

我们假设慢指针的速率为1，快指针的速率为2。慢指针走过的路程为s, 快指针走过的路程为f。快指针走过的环的圈数为k。

这里可以假设起点到入口点的距离非常长，而环的长度非常小，这时候就有可能在快慢指针相遇前，快指针在环里走了非常多圈。

为了方便理解，这里再假设起点到入口节点的距离为a，入口节点到相遇节点的距离为b，环中剩余距离为c，环的长度为n。如下图

image-20210928200022776

这时候我们可以得到一些等式，如下:

• s = a + b
• f = a + b + nk = s+nk
• t_s = t_f (t_s代表慢指针所用时间，t_f代表快指针所用时间)
• v_s = 1, v_f=2 (v_s代表慢指针的速率，v_f代表快指针的速率)
• t_s=\frac{s}{v_s}, t_f=\frac{f}{v_f}

先联立一下这5个式子，s先不展开，得到s = n*k， k\in[1,+\infty] (这里注意k取值，快指针至少比慢指针快一圈)

根据题意，我们应该再可以挖掘一些与变量a有关等量关系。

• 这里慢指针在相遇后，继续顺指针再走c个距离，则可以到达入口点。
• 假设一个新指针new_ptr(不是快指针，也不是慢指针，是我们创建的第三个指针)从起点出发，若要到达入口点，则这个指针的路程应该是a+n*k,k\in[0,+\infty](这里同样注意k的取值，因为只要到达入口点即可，所以走过的环的圈数应该可以是任意圈)

这里出现了两个k，为了便于区分，我们修改下等式s = nk_1， k_1\in[1,+\infty] ，a+nk_2,k_2\in[0,+\infty]

• slow+(nk_1+c) = new_ptr+(a+nk_2)。这个等式什么意思呢？就是若慢指针和新指针要在入口点这个地方相遇。则慢指针从起点出发，走过了nk_1+c距离后，到达入口点，以及新指针从起点出发，走过a+nk_2距离后，到达入口点，他们俩在入口点这个地方相遇。(不是很严谨，因为理论上没有重载+号是不能直接+的)。由于slow指针和new_ptr都是从起点出发，因此有nk_1+c = a+nk_2。这里我们再利用k_2\in[0,+\infty]，k_1\in[1,+\infty] 的性质，令k_2=k_1，就能得到等式c=a。

这里为什么可以令k_2=k_1？想一下，在第一步判断是否存在环中，快慢指针相遇的时候k_1是不是已经确定了？而这时候变量k_2是可以任意取值的，并且k_2的取值范围包括了k_1的取值范围！因此只要直接令k_2=k_1即可消除。

得到c=a后，我们就可以开始了。

3. 做法

• 快慢指针前进，相遇后停下来。
• 创建一个新指针从起点出发，新指针和慢指针同时前进，只要相遇了，则相遇点就是入口点。(当然也可以创建一个变量cnt记录走了多少步后相遇，cnt的值就是上面a的大小，但这里只需要返回节点所以就不需要了)

c/c++代码

/**
 * 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) {
        if(head == nullptr || head->next == nullptr) {
            return nullptr;
        }
        ListNode *slow = head, *fast = head;
        while(fast != nullptr && fast->next != nullptr) {		//如果不存在环，则退出
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow) {									//快慢指针相遇
                ListNode* new_ptr = head;						//新指针
                while(new_ptr != slow) {						//新指针，慢指针未相遇，继续前进
                    new_ptr = new_ptr->next;
                    slow = slow->next;
                }
                return slow;
            }
        }
        return nullptr;
    }
};

时间复杂度O(N)

空间复杂度O(1)