题解 | #链表中环的入口节点#

题目主要信息:

给定一个链表，首先判断其是否有环，然后找到环的入口

具体思路:

根据题干，不说别的，我们能发现这道题需要完成两个任务：

判断链表是否有环。
在有环的链表中找到环的入口。

对于第一个任务，可以参考判断链表中是否有环，主要思想是利用环没有末尾NULL，后半部分一定是环，然后快慢双指针相遇就代表有环。（具体分析可以点进链表观看）

alt

那我们现在假定已经是一个有环的链表了，那么这个链表中怎么找到环的入口呢？在慢指针进入链表环之前，快指针已经进入了环，且在里面循环，这才能在慢指针进入环之后，快指针追到了慢指针，不妨假设快指针在环中走了 $n$ 圈，慢指针在环中走了 $m$ 圈，它们才相遇，而进入环之前的距离为 $x$ ，环入口到相遇点的距离为 $y$ ，相遇点到环入口的距离为 $z$ 。快指针一共走了 $x + n (y + z) + y$ 步，慢指针一共走了 $x + m (y + z) + y$ ，这个时候快指针走的倍数是慢指针的两倍，则 $x + n (y + z) + y = 2 (x + m (y + z) + y)$ ，这时候 $x + y = (n - 2 m) (y + z)$ ，因为环的大小是 $y + z$ ，说明从链表头经过环入口到达相遇地方经过的距离等于整数倍环的大小：那我们从头开始遍历到相遇位置，和从相遇位置开始在环中遍历，会使用相同的步数，而双方最后都会经过入口到相遇位置这 $y$ 个节点，那说明这 $y$ 个节点它们就是重叠遍历的，那它们从入口位置就相遇了，这我们不就找到了吗？

step 1：使用判断链表中是否有环中的方法判断链表是否有环，并找到相遇的节点。
step 2：慢指针继续在相遇节点，快指针回到链表头，两个指针同步逐个元素逐个元素开始遍历链表。
step 3：再次相遇的地方就是环的入口。

具体过程如下图所示：

alt

代码实现:

class Solution {
public:
    ListNode* hasCycle(ListNode *head) { //判断有没有环，返回相遇的地方
        if(head == NULL) //先判断链表为空的情况
            return NULL;
        ListNode* fast = head; //快慢双指针
        ListNode* slow = head;
        while(fast != NULL && fast->next != NULL){ //如果没环快指针会先到链表尾
            fast = fast->next->next; //快指针移动两步
            slow = slow->next; //慢指针移动一步
            if(fast == slow) //相遇则有环
                return slow; //返回相遇的地方
        }
        return NULL; //到末尾则没有环
    }
    
    ListNode *detectCycle(ListNode *head) {
        ListNode* slow = hasCycle(head);
        if(slow == NULL) //没有环
            return NULL;
        ListNode* fast = head; //快指针回到表头
        while(fast != slow){ //再次相遇即是环入口
            fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }
};

复杂度分析：

时间复杂度： $O (n)$ ，最坏情况下遍历链表两次
空间复杂度： $O (1)$ ，使用了常数个指针，没有额外辅助空间