# Q142. Linked List Cycle II

直达：<https://leetcode.com/problems/linked-list-cycle-ii/description/>

Given a linked list, return the node where the cycle begins. If there is no cycle, return`null`.

**Note:**&#x44;o not modify the linked list.

**Follow up**:\
Can you solve it without using extra space?

## 分析

设置三个指针，快指针fast每次遍历两个节点，慢指针slow1，slow2每次遍历两个节点。

开始的时候fast和slow1先从头节点开始遍历，相遇的时候fast走的距离是slow1的两倍，如下图:

![](/files/-M9D-7QvV4tShSq1ytkF)

假设非环链表部分的长度是x，环的周长是y，fast和slow1在d处相遇，此时fast比slow1多走了一个圆环，于是有

2 \* (x+d) = x+d+y

化简得：

x = y-d

第二轮遍历的时候slow2从头结点开始遍历，slow1从d处开始遍历，当遍历到环起始点的时候，因为x=y-d，所以两指针会在这个地方相遇。

## C++代码

```cpp
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(!head) return NULL;
        ListNode* slow1 = head;
        ListNode* slow2 = head;
        ListNode* fast = head;
        while(fast && fast->next){
            fast = fast->next->next;
            slow1 = slow1->next;
            if(fast == slow1){
                while(slow2 != slow1){
                    slow2 = slow2->next;
                    slow1 = slow1->next;
                }
                return slow2;
            }
        }
        return NULL;
    }
};
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://senliuy.gitbook.io/leetcode/chapter1/12-lian-biao/q142-linked-list-cycle-ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.