141. 环形链表

Origin: LeetCode 141

题目描述

给定一个链表的头节点 head，判断链表中是否有环。如果链表中存在环，返回 true；否则返回 false。

示例

Input: head = [3, 2, 0, -4]，pos = 1（尾节点连接到 index 1） Output: true

3 → 2 → 0 → 4
    ↑__________|

Input: head = [1]，pos = -1 Output: false

约束

• 链表中节点数范围是 [0, 10
• -10^5 <= Node.val <= 10
• pos 为 -1 或者链表中的有效索引
• 要求 O(1) 空间

关键信息

• 你做过 HackerRank 第 24 题（图论环检测三色标记），但那是图，这是链表
• 快慢指针：慢走 1 步，快走 2 步，相遇则有环
• 你有题型笔记”快慢指针”

Resolution

我的解法

function hasCycle(head: ListNode | null): boolean {
    if (!head || !head.next) return false
 
    let fast: ListNode | null = head.next.next
    let slow: ListNode | null = head
    while (fast?.next) {
        if (fast === slow) {
            return true
        }
        fast = fast?.next?.next || null
        slow = slow?.next || null
    }
    return false
}

解题思路

快慢指针。慢走 1 步，快走 2 步。有环必相遇（速度差 1，每轮追近 1 步，不会跨过），无环快指针先到 null。

关键：fast === slow 比的是引用（内存地址），不是 val。即使所有节点 val 相同，引用不同不会误判。

复杂度

• 时间：O(n)
• 空间：O(1)