环形链表142

Algorithm 评论

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

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

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

解题关键是理解 非环部分的长度与相遇点到环起点那部分环的长度 是相等的 这个数学关系

假设非环部分长度为x, 从环起点到相遇点的长度为y , 环的长度为c

慢指针(slow)走过的长度可以表示为``ds = x + n1 * c + y, 快指针(fast) 的速度是慢指针的两倍, 意味着 快指针走过的长度为df = 2(x + n1 * c + y)`

还有一个约束是, fast 走过的路程一定比slow走的路程多出环长度的整数倍(记为n2 * c)

所以 

1
2
3
df - ds = n2 * c
2(x + n1 * c + y) - (x + n1 * c + y) = n2 * c
x + n1 * c + y = n2 * c

解读下第三步的等式: 非环部分的长度 + 环起点到相遇点之间的长度 就是环的整数倍

意味着, 当以环的起点为原点时, 已经走过y(即前面从环起点到相遇点的长度)的前提下, 如果再走x , 就刚好走了很多圈(n2 * c). *”很多圈” 的意思, 就是从原点再到原点, 终点的位置和起点的位置重合.*

怎么才能再走x呢? 让一个指针从head 开始走, 另一个指针从相遇点开始走, 等这两个指针相遇, 就是走了x. 如果不能理解为何相遇恰好就在上面说的原点处, 应该反复琢磨斜体”很多圈”那句话

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func detectCycle(head *ListNode) *ListNode {
	fast, slow := head, head
	
	for fast != nil && fast.Next != nil && fast.Next.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
		if fast == slow {
			fast = head
			for fast != slow {
				fast = fast.Next
				slow = slow.Next
			}
			return fast
		}
	}
	return nil
}