时间轴

2026-03-13

init

题目：

P142 环形链表 II

https://leetcode.cn/problems/linked-list-cycle-ii/description/?envType=study-plan-v2&envId=top-100-liked

第一次相遇，快指针走了2 * k步，慢指针走了 k 步，记环外长度 m, 环长 L

快指针多走了n圈(nL)即 k = nL , 即慢指针走了 nL 步

慢指针再走m步，则共走 m+nL 步到达 m+nL= 环入口

注意下面那个循环不要用do while，因为一个链表可能是个循环链表，环外长度为0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

struct ListNode {
        int val;
        ListNode *next;
        ListNode(int x)
                : val(x)
                , next(nullptr)
        {
        }
};

class Solution {
    public:
        ListNode *detectCycle(ListNode *head)
        {
                if (head == nullptr)
                        return nullptr;
                ListNode *low = head, *fast = head;

                do {
                        if (fast->next == nullptr || fast->next->next == nullptr)
                                return nullptr;

                        fast = fast->next->next;
                        low = low->next;

                } while (low != fast);

                // low == fast

                low = head;
                while (low != fast) {
                        fast = fast->next;
                        low = low->next;
                }

                return low;
        }
};