LeetCode 141. 环形链表

2026-09-09 HGNULB 约 3 分钟

文章信息 25 个分类 5 个标签

分类

LeetCode CodeTop 简单已解决已掌握 200-500 字节跳动微软美团阿里巴巴快手腾讯猿辅导百度滴滴京东华为拼多多网易小米虾皮哔哩哔哩作业帮 LeetCode 热题 100 面试经典 150 题

题目描述

✅ 141. 环形链表

题意分析

给定链表头节点，判断链表中是否存在环，返回布尔值即可——本题不要求找出环的入口节点，那是 142 题的任务，这里只需要回答「有没有」。

题面中的 pos 只用于评测端构造用例，并不会作为参数传入，函数能拿到的只有 head。判断依据必须是节点引用（同一个节点被第二次到达），不能依赖节点值，因为不同节点完全可以有相同的值。

进阶要求用常数内存解决，这是一个明确信号：存在不借助额外容器的判法。边界上，空链表和单节点无环链表（next 为空）都应返回 false。

解法：Floyd 快慢指针

核心思路

慢指针每次走一步，快指针每次走两步。无环时快指针会先到达链表末尾；有环时两者进入环后，快指针会从后方追上慢指针。整个过程只需要两个指针。

解题步骤

将快、慢指针都初始化为头节点。

当快指针及其后继都非空时，慢指针走一步、快指针走两步。

移动后若两个指针引用相同，返回 true。

循环正常结束说明快指针到达链表末尾，返回 false。

代码实现

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }
}

func hasCycle(head *ListNode) bool {
    slow := head
    fast := head

    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        if slow == fast {
            return true
        }
    }
    return false
}

复杂度分析

时间复杂度：$O(n)$，每个指针的移动次数都与链表长度同阶。

空间复杂度：$O(1)$，只使用快、慢两个指针。

关键点总结

判断相遇必须比较节点引用，而不是节点值。

快指针每次走两步，循环条件必须同时检查 fast 和 fast.next。

两个指针从同一起点出发时，应先移动再判断是否相遇。

易错点总结

只检查 fast != null 就访问 fast.next.next，可能触发空指针异常。

移动前比较两个同起点的指针，会把任意非空链表误判为有环。

用节点值判断相遇，会把值相同的不同节点误认为同一节点。

本题只判断是否有环；寻找环入口还需要相遇后的第二阶段。

相似题目

题目	难度	考察点
142. 环形链表 II	中等	相遇后推导环入口
202. 快乐数	简单	数字迭代构成的隐式链判环
287. 寻找重复数	中等	数组下标映射的隐式环
457. 环形数组是否存在循环	中等	带方向约束的环判定
LCR 022. 环形链表 II	中等	环入口题的镜像练习
面试题 02.08. 环路检测	中等	环入口结论的面试金典版