1. 技巧分析
快慢指针赛跑: 同时从表头出发, 慢指针 slow 步长为 1, 快指针 fast 步长为 2.
1.1 环的判断
若有环存在, fast 与 slow 必在环内相遇: 当 slow 进入环时, fast 已在环内, 此时 fast 追 slow, 因每一步都会缩短距离, 必然能追上.
也就是说, 如果 fast 与 slow 始终未相遇, 必不存在环.
1.2 环的入口
如图, 假设 fast 与 slow 从表头 head 开始走, 在 meet 处首次相遇. x 为环的入口, a, b, c分别表示单链表方向上表头至环入口, 环入口至相遇点, 相遇点至环入口的距离.
slow 初到 meet 时, fast 已经走了 a + b + n(b + c) (n为正整数).
因为 fast 的速度是 slow 的两倍, 且二者同时出发, 所以 fast 所走路程也是 slow 的两倍: a + b + n(b + c) = 2(a + b), 即 a = c + (n - 1)(b + c).
而 b + c 是环的长度, 于是此时让 slow, fast 分别以相同速度(步长为一)从 head 和 meet 同时出发, 必将在环入口处 x 相遇.
1.1 与 1.2 的复杂度都是O(n): 最坏情况即 slow 的每次行程都是走完一遍链表.
2. 判断链表是否有环
题目描述
给定一个链表，判断链表中是否有环。
解
实现 1.1 即可.
def hasCycle(self, head):
"""
:type head: ListNode
:rtype: bool
"""
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
3. 求环的入口
题目描述
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
说明：不允许修改给定的链表。
解
实现 1.2 即可.
def detectCycle(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
break
if fast is None or fast.next is None:
return None
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
return slow
4. 求数组中的重复数字
题目描述
给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
示例 1:
输入: [1,3,4,2,2]
输出: 2
示例 2:
输入: [3,1,3,4,2]
输出: 3
说明：
- 不能更改原数组（假设数组是只读的）。
- 只能使用额外的 O(1) 的空间。
- 时间复杂度小于 O(n^2) 。
- 数组中只有一个重复的数字，但它可能不止重复出现一次。
转换成求环的入口问题
考虑序列:
x(0) = nums[0]
x(1) = nums[x(0)]
x(2) = nums[x(1)]
...
x(n) = nums[x(n-1)]
这 n+1 个数的取值都来自数组 nums 的元素, 也就是最多取 n 个不同的值, 必存在两数相等.
可以想象, 如果 x(i) == x(k) (i < k <= n), 那么0, x(0), ... , x(i), ... , x(k) 的关系等价于一个有环的链表:
其中 ~.next 等价于 nums[~], 且表头 0 不会是环的起点(任一 x(j) 的取值范围是{1, 2, ... , n}). 环入口 x(i) 即为所求重复数.
于是原问题转换成求链表中的环的入口问题. 复杂度O(n).
解
def findDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
slow = fast = 0
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break
slow = 0
while slow != fast:
slow = nums[slow]
fast = nums[fast]
return slow
乌龟为什么能追上兔子？答：因为有环。
