142. 环形链表 II(Medium)

题目描述

给定一个链表，如果有环路，找出环路的开始点。

样例

输入是一个链表，输出是链表的一个节点。如果没有环路，返回一个空指针。

题解

暴力解法

最简单的做法是通过 hash 表寻找，则空间复杂度为 O(n)，那有没有更好的解法？得空间复杂度满足 O(1)，时间复杂度满足O(n)

快慢指针、Floyd判圈法、龟兔赛跑算法

由于链表寻找环路的问题，是一个计算机领域经常遇到的问题，所以有一个通用的解法——快慢指针（Floyd 判圈法）。此算法解决了两个问题，第一是如何检测环，第二个是找到环的入口节点。

问题1：Cycle detection，循环检测

给定两个指针， 分别命名为 slow 和 fast，起始位置在链表的开头。每次 fast 前进两步，slow 前进一步。如果 fast 可以走到尽头，那么说明没有环路；如果 fast 可以无限走下去，那么说明一定有环路，且一定存 在一个时刻 slow 和 fast 相遇。

问题2：求环的起点

当 slow 和 fast 第一次相遇时，我们将 fast 重新移动到链表开头，并 让 slow 和 fast 每次都前进一步。当 slow 和 fast 第二次相遇时，相遇的节点即为环路的开始点。

伪代码

# link: https://en.wikipedia.org/wiki/Cycle_detection
# 龟兔算法
def floyd(f, x0): # f 状态， x0 起点
    tortoise = f(x0) # 龟走一步
    hare = f(f(x0)) # 兔走两步
    while tortoise != hare:
        tortoise = f(tortoise)
        hare = f(f(hare))

    mu = 0 
    tortoise = x0 # 龟移到头部
    while tortoise != hare: 
        tortoise = f(tortoise)
        hare = f(hare)   # 龟兔同速
        mu += 1 # mu 代表了环的入口位置
 
    # 求环的长度
    lam = 1
    hare = f(tortoise)
    while tortoise != hare:
        hare = f(hare)
        lam += 1
 
    return lam, mu # 环的长度, 入口的位置

证明

JS老毕 这一部分写的非常好，通俗易懂

Python示例

# hash table 
class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        visited = {}
        while head and not head in visited:
            visited[head] = True
            head = head.next 
        return head

# Floyd 判断法
# 这个Python写法比较难
class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        fast = slow = head 
        while True:
            if not (fast and fast.next): return # 注意，这里是return，因为没有环
            slow = slow.next 
            fast = fast.next.next
            if slow == fast: break # 寻找入环的第一个节点
        fast = head 
        while fast != slow:
            slow, fast = slow.next, fast.next
        return fast  

C++示例

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *slow = head, *fast = head;
        // 判断是否存在环路
        do {
            if (!fast || !fast->next) return nullptr;
            fast = fast->next->next;
            slow = slow->next;
        } while (slow != fast);
        // 如果存在，查找环路节点
        fast = head;
        while (fast != slow) {
            slow = slow->next;
            fast = fast->next;
        }
        return fast;
    }
};

Go 示例

func detectCycle(head *ListNode) *ListNode {
   if head == nil || head.Next == nil { return nil } 
   slow := head.Next 
   fast := slow.Next
   for fast != nil && fast.Next != nil {
       slow = slow.Next
       fast = fast.Next.Next 
       if fast == slow { break }
   }
   if fast == nil || fast.Next == nil { return nil}
   fast = head 
   for fast != slow {
       fast = fast.Next
       slow = slow.Next
   }
   return fast 
}