# C++实现LeetCode(142.单链表中的环之二)

[LeetCode] 142. Linked List Cycle II 单链表中的环之二 Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

## [LeetCode] 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.

Example www.cppcns.com2:

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.

Example 3:

Input: head = [1], pos = -1

Output: no cycle

Explanation: There is no cycle in the linked list.

Can you solve it without using extra space?

```class Solution {
public:
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) break;
}
if (!fast || !fast->next) return NULL;
while (slow != fast) {
slow = slow->next;
fast = fast->next;
}
return fast;
}
};```

github 同步地址：

https://github.com/grandyang/leetcode/issues/142

Find the Duplicate Number