题目

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

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

示例 1：

test1

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

test2

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

test3

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

提示：

链表中节点的数目范围是 [0, 104]
-105 <= Node.val <= 105
pos 为 -1 或者链表中的一个 有效索引 。

进阶：你能用 O(1)（即，常量）内存解决此问题吗？

解题思路

书接上回 环形链表1，这次标注了不能修改链表的要求，并且要求返回入环的第一个节点，所以不能直接修改链表的 next 指针了。先用 HashSet 的方法来解决问题，遍历链表，将访问过的节点存入 HashSet 中，如果发现当前节点已经在 HashSet 中，则说明有环，返回当前节点；如果遍历完链表都没有发现重复的节点，则返回 null。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func detectCycle(head *ListNode) *ListNode {
	nodeMap := make(map[*ListNode]bool)
	for head != nil {
		if _, ok := nodeMap[head]; ok {
			return head
		}
		nodeMap[head] = true
		head = head.Next
	}

	return nil
}

当然这个方法的空间复杂度是 O(n)，不符合题目要求的 O(1) 空间复杂度。所以还是考虑快慢针，这里的问题在于当发现有环的时候并不是入环的第一个节点，所以需要思考如何找到入环的第一个节点。

说实话这如果不刷题还真的很难想到这里，仔细想的话，会发现快慢针有一个隐含条件，就是当fast和slow相遇的时候，fast 走过的距离是slow走过的距离的两倍。而根据该条件就可以进行如下推导：

circularlinkedlist

  1. 假设链表中环外的距离为 a（也就是：链表头到入环点的距离为 a），入环点到相遇点的距离为 b，相遇点到入环点的距离为 c。
  2. fast 指针走过的距离为 ，其中 n 是环的圈数。
  3. slow 指针走过的距离为 ，其中 m 是环的圈数。
  4. 由于 fast 指针走过的距离是 slow 指针走过的距离的两倍，所以可以得到如下方程：
  5. 化简后可以得到： 即为

基于 ，观察可得 b+c 就是环的周长，a 就是入环点到相遇点的距离，所以可以得到如下结论：无论fast 和 slow 指针相遇在环的哪个位置，在相遇的时候一个指针从链表头出发，另一个指针从相遇点出发，两个指针相遇的地方就是入环点。

所以可以得到如下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func detectCycle(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return nil
	}

	for slow, fast := head, head; fast != nil && fast.Next != nil; {
		slow = slow.Next
		fast = fast.Next.Next
		if slow == fast {
			for head != slow {
				head = head.Next
				slow = slow.Next
			}
			return head
		}
	}

	return nil
}