[LeetCode 141, 142, 287] 链表求环问题

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

说明：

1. 不能更改原数组（假设数组是只读的）。
2. 只能使用额外的 O(1) 的空间。
3. 时间复杂度小于 O(n^2) 。
4. 数组中只有一个重复的数字，但它可能不止重复出现一次。

转换成求环的入口问题

考虑序列:
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

乌龟为什么能追上兔子？答：因为有环。