1、思路

• 首先要确定一点，当链表中有环时，遍历链表是走不到尽头的。如果遍历到空节点，说明链表无环；

• 用一快一慢两个指针从链表头开始遍历，快指针每次走2步，慢指针每次走1步；

• 进入环后，快指针每次会追上慢指针1步，所以若链表有环，快指针一定会追上慢指针；

• 当两个指针相等时，假设慢指针走了k步，那么快指针一定走了2k步，且此时快指针超过了慢指针若干圈，而且是正好超过整数圈，所以它们才会相遇。则快指针比慢指针多走的这k步，是环中节点个数的整数倍；

• 这时把其中一个指针挪到链表头部继续遍历，两指针每次走一步，当它们再次相遇时，相遇的节点就是链表环入口。因为当其中一个指针走到环入口时，另一个指针正好比它多走了k步（即正好多走了若干整数圈），所以它们会相遇。

2、代码

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

        auto fast = head, slow = head;
        while (fast)
        {
            fast = fast->next;
            slow = slow->next;

            if (fast) fast = fast->next;
            else return nullptr;

            if (fast == slow)           //两指针第一次相遇，此时fast比slow多走了若干整数圈
            {
                slow = head;            //其中一个指针挪到链表头部继续遍历
                while (fast != slow)    //判断两指针是否第二次相遇
                {
                    fast = fast->next;
                    slow = slow->next;
                }

                return fast;
            }
        }

        return nullptr;
    }
};

这个题我在面百度IDG智驾技术部后端的时候，被问到过，要求解释清楚其数学原理。