23.链表中环的入环点 (Easy)*

题目描述*

一个链表中包含环，请找出该链表的环的入口结点。要求不能使用额外的空间。

代码*

这个题也做过，可以通过数学证明，快慢指针的相遇点到入环点的距离与头结点到入环点的距离相等，即有以下。

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *fast = head, *slow = head;
        while(fast != nullptr && fast->next != nullptr) {
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow) {
                slow = head;
                while(slow != fast) {
                    slow = slow->next;
                    fast = fast->next;
                }
                return slow;
            }
        }
        return nullptr;
    }
};

最后更新: July 23, 2022