## 题目地址(142. 环形链表 II)

https://leetcode-cn.com/problems/linked-list-cycle-ii/

## 题目描述

```
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。

说明：不允许修改给定的链表。

进阶：

你是否可以使用 O(1) 空间解决此题？
```

## 哈希法

### 思路

1. 遍历整个链表,同时将每个节点都插入哈希表,
2. 如果当前节点在哈希表中不存在,继续遍历,
3. 如果存在,那么当前节点就是环的入口节点

- 伪代码:

```js
data = new Set() // 声明哈希表
while head不为空{
  if 当前节点在哈希表中存在{
    return head // 当前节点就是环的入口节点
  } else {
    将当前节点插入哈希表
  }
  head指针后移
}
return null // 环不存在
```

### 代码

- 代码支持: JS

JS Code:

```js
let data = new Set();
while (head) {
  if (data.has(head)) {
    return head;
  } else {
    data.add(head);
  }
  head = head.next;
}
return null;
```

**复杂度分析**

- 时间复杂度：$O(N)$
- 空间复杂度：$O(N)$

## 快慢指针法

### 思路

1. 定义一个 fast 指针,每次**前进两步**,一个 slow 指针,每次**前进一步**
2. 当两个指针相遇时
   1. 将 fast 指针指向链表头部,同时 fast 指针每次只**前进一步**
   2. slow 指针继续前进,每次**前进一步**
3. 当两个指针再次相遇时,当前节点就是环的入口

![](https://tva1.sinaimg.cn/large/007S8ZIlly1gfigbvzje1j30ky0bhq3x.jpg)
（图 6）

为什么第二次相遇的点为环的入口? 原因如下：

- **第一次相遇时**
- 慢指针移动的距离为 s1 = A + B + n1 \* L
- 快指针移动的距离为 s2 = A + B + n2 \* L
- 快指针是慢指针速度的两倍,所以 s2 = 2\* s1
- A + B + n2 * L = 2A + 2B + n1 * L ===> A = -B + (n2 - n1) \* L
- 因为圆的性质 (n2 - n1) \* L ===> 绕圆 (n2 - n1) 圈 ===> 0
- A = -B + (n2 - n1) \* L ===> A = -B
- 即在第一次相遇点, 向前走 A 步 ===> 向后走 B 步
- **第一次相遇后**
- 快指针从头节点走 A 步会到达环的入口
- 慢指针从第一次相遇点走 A 步,相当于向后走 B 步,也会到达环的入口

- 伪代码：

```jsx
fast = head
slow = head //快慢指针都指向头部
do {
  快指针向后两步
  慢指针向后一步
} while 快慢指针不相等时
if 指针都为空时{
  return null // 没有环
}
while 快慢指针不相等时{
  快指针向后一步
  慢指针向后一步
}
return fast
```

### 代码

- 语言支持: JS, Go, PHP, CPP

JS Code：

```js
if (head == null || head.next == null) return null;
let fast = (slow = head);
do {
  if (fast != null && fast.next != null) {
    fast = fast.next.next;
  } else {
    fast = null;
  }
  slow = slow.next;
} while (fast != slow);
if (fast == null) return null;
fast = head;
while (fast != slow) {
  fast = fast.next;
  slow = slow.next;
}
return fast;
```

Go Code:

```go
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func detectCycle(head *ListNode) *ListNode {
	// x 到环的距离; y 环的长度; z p/q环上相遇的位置; a/b/c 正整数, 表示绕环整数圈
	// k=x+ay+z; 2k=x+by+z => x+z=cy, x=cy-z
	p := head // 快指针, 2倍速
	q := head // 慢指针, 1倍速
	k := true // 第一次执行
	for p != q || k {
		k = false
		if p == nil || p.Next == nil {
			return nil
		}
		p = p.Next.Next
		q = q.Next
	}
	// 由于 x=cy-z, p 重置为 head, q 此时在 z 处, 则正好在环起点相遇
	p = head
	for p != q {
		p = p.Next
		q = q.Next
	}
	return p
}
```

PHP Code:

```php
/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val) { $this->val = $val; }
 * }
 */
class Solution
{
    /**
     * @param ListNode $head
     * @return ListNode
     */
    function detectCycle($head)
    {
        // x 到环的距离; y 环的长度; z p/q环上相遇的位置; a/b/c 正整数, 表示绕环整数圈
        // k=x+ay+z; 2k=x+by+z => x+z=cy, x=cy-z
        $p = $q = $head; // $p 快指针, 2倍速; $q 慢指针, 1倍速
        $k = true; // 第一次执行
        while ($p != $q || $k) {
            $k = false;
            if (!$p || !$p->next) return null;
            $p = $p->next->next;
            $q = $q->next;
        }
        // 由于 x=cy-z, p 重置为 head, q 此时在 z 处, 则正好在环起点相遇
        $p = $head;
        while ($p != $q) {
            $p = $p->next;
            $q = $q->next;
        }
        return $p;
    }
}
```

CPP Code:

```cpp
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if (!head) return NULL;
        auto p = head, q = head;
        while (p && p->next) {
            p = p->next->next;
            q = q->next;
            if (p == q) break;
        }
        if (!p || !p->next) return NULL;
        p = head;
        for (; p != q; p = p->next, q = q->next);
        return p;
    }
};

```

**复杂度分析**

- 时间复杂度：$O(N)$
- 空间复杂度：$O(1)$
