141. 环形链表

题目链接：https://leetcode.cn/problems/linked-list-cycle/

代码

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function hasCycle(head: ListNode | null): boolean {
    let a: ListNode | null = head;
    let b: ListNode | null = head;
    while(b && b.next){
        a = a!.next;
        b = b.next.next;
        if(a === b){
            return true;
        }
    }
    return false;
}

思路

使用快慢指针（Floyd 判圈算法）来检测链表中是否存在环：

初始化两个指针：
- a（慢指针）：每次移动一步
- b（快指针）：每次移动两步
遍历链表：
- 如果快指针 b 或 b.next 为 null，说明链表无环，返回 false
- 如果快慢指针相遇（a === b），说明链表有环，返回 true
原理：
- 如果链表有环，快指针最终会追上慢指针
- 如果链表无环，快指针会先到达链表末尾

这是检测链表环的经典算法，也是后续题目（如 142 题）的基础。

时间复杂度 $O (n)$ ，其中 $n$ 是链表的长度
空间复杂度 $O (1)$

141. 环形链表 ​

代码 ​

思路 ​

141. 环形链表

代码

思路