【LeetCode热题100】【链表】环形链表 II

叶茂林

发布于 2024-04-13 08:10:49

630

发布于 2024-04-13 08:10:49

如果有环，快慢指针一定会在环内相遇，假设从链表头到环入口距离为a，快慢指针相遇处距入口距离为b，那么慢指针走了a+b，而快指针走了2a+2b，记相遇处绕回到入口处距离为c，那么快指针多走了一圈，即c+b，即a=c，此时让一个指针从链表头开始走c步，一个指针同时在相遇处走c步，那么他们会在入口相遇

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

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2024-04-12，如有侵权请联系 cloudcommunity@tencent.com 删除

leetcode