# 142. Linked List Cycle II

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

To represent a cycle in the given linked list, we use an integer `pos` which represents the position (0-indexed) in the linked list where tail connects to. If `pos` is `-1`, then there is no cycle in the linked list.

**Note:** Do not modify the linked list.

**Example 1:**

```
Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.
```

![](https://assets.leetcode.com/uploads/2018/12/07/circularlinkedlist.png)

**Example 2:**

```
Input: head = [1,2], pos = 0
Output: tail connects to node index 0
Explanation: There is a cycle in the linked list, where tail connects to the first node.
```

![](https://assets.leetcode.com/uploads/2018/12/07/circularlinkedlist_test2.png)

**Example 3:**

```
Input: head = [1], pos = -1
Output: no cycle
Explanation: There is no cycle in the linked list.
```

![](https://assets.leetcode.com/uploads/2018/12/07/circularlinkedlist_test3.png)

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

## Thoughts

linked list里如有环，返回环开始的位置。两个指针从head开始快慢跑，在一个环上跑得快的肯定会在某点追上跑的慢的。假设已经相遇，a: 环之前长度, c: 环长度, s: slow走的步数, k: 环起点后第k步相遇，x: slow跑得环的圈数，y: fast跑得圈数，因此 s=a+xc+k, 2s=a+yc+k, 合并得k = (y-2x)b-a, 即slow还差a步则走的步数刚好又是环长的倍数，也就是说slow里环终点(起点)还差a步，因此让slow和head再走a步它们刚好会相遇。

## Code

```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) {
        auto slow = head, fast = head;
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) {
                while (head != slow) {
                    head = head->next;
                    slow = slow->next;
                }
                return head;
            }
        }
        return nullptr;
    }
};
```

```java
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = slow;
        while (slow != null && fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (slow == fast) {
                while (head != slow) {
                    head = head.next;
                    slow = slow.next;
                }
                return slow;
            }
        }

        return null;
    }
}
```

## Analysis:

Errors:

1. ~~终止条件是slow\.next == head， 不是slow == head或者head.next == slow~~

TC: O(n)

我们来分析一下，时间复杂度取决于slow到底走了多少步，即a + xc + k 和总结点数N关系。\
主要就是看x是多少。\
我们知道x取决去fast什么时候能追上slow. 由于fast先走，等slow进环时fast早已在环中等候了。\
那在一个环里slow最多能走多少就被fast追上呢？答案是不到一个环。\
我们假设最差的情况，即fast和slow刚好差一个环的位置，那么s\_f = s + c, 即2s = s + c,\
s = c.也就是说在fast和slow在环中起始位置刚好差一个环时，slow最多走一个环就会被追上。\
又由于fast和slow实际最多只能差c - 1, 所以x < 1, s < a+2c。整个算法是O(N)级别。


---

# 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://hao-fu-1.gitbook.io/oj/multiple-pointers/floyd-cycle/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.