环形链表 II | 秋招知识库

题目链接 · 灵神原题解（署名来源）

请先完成上一题 141. 环形链表。本题继续使用快慢指针的做法。

图解环形链表

注 1： $k c - a$ 是从入环口开始的步数。由于 $(k c - a) + a = k c$ ，所以从 $k c - a$ 开始，再走 $a$ 步，就恰好走了 $k$ 圈，回到入环口。

注 2：慢指针从相遇点开始，移动 $a$ 步后恰好走到入环口，但在这个过程中，可能会多次经过入环口。

注 3：这个算法叫做 Floyd 判圈算法。

本题视频讲解【基础算法精讲 07】

Python 解法1C++ 解法1

python

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if fast is slow:  # 相遇
                while slow is not head:  # 再走 a 步
                    slow = slow.next
                    head = head.next
                return slow
        return None

cpp

// C++ 版待补充

C++ 解法2

cpp

class Solution {
public:
    ListNode* detectCycle(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (fast == slow) { // 相遇
                while (slow != head) { // 再走 a 步
                    slow = slow->next;
                    head = head->next;
                }
                return slow;
            }
        }
        return nullptr;
    }
};

复杂度分析

时间复杂度： $O (n)$ ，其中 $n$ 是链表的长度。理由见本题视频讲解【基础算法精讲 07】。
空间复杂度： $O (1)$ 。

专题训练

见下面链表题单的「§1.6 快慢指针」。

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

复杂度分析 ​

专题训练 ​

分类题单 ​

复杂度分析

专题训练

分类题单