0%

### 题目描述

Given `head`, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the `next` pointer. Internally, pos is used to denote the index of the node that tail’s `next` pointer is connected to. Note that `pos` is not passed as a parameter.

Return `true` if there is a cycle in the linked list. Otherwise, return `false`.

### 例子

#### 例子 1

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

#### 例子 2

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

#### 例子 3

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

### Follow Up

Can you solve it using `O(1)` (i.e. constant) memory?

### Constraints

• The number of the nodes in the list is in the range `[0, 10^4]`
• `-10^5 <= Node.val <= 10^5`
• `pos` is `-1` or a valid index in the linked-list.

### 解题思路

• 假设快指针距离慢指针只剩一步或者两步（假设是三步的话，下一次迭代之后距离会变为两步因此可以归为这一类）
• 假设只剩一步，那么下一次迭代，快慢指针会重合
• 假设只剩两步，那么下一次迭代之后会只剩一步，因此再下一次迭代还是会重合

• 时间复杂度: O(n)
• 空间复杂度: O(1)

GitHub 代码同步地址： 141.LinkedListCycle.cpp

GitHub: Leetcode-C++-Solution