当前位置：首页 > java >正文

141. 环形链表

java 2025/6/16 7:26:48

一、问题描述

二、解题思路

三、代码

四、复杂度分析

一、问题描述

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

二、解题思路

✅ 解题思路：快慢指针（Floyd 判圈法）

核心思想：

我们设置两个指针：

slow：每次走一步
fast：每次走两步

如果链表中有环，fast 一定会在环中追上 slow，就像赛道上跑步，快的迟早会追上慢的。

如果链表没有环，fast 会先到达 nullptr（链表尾），说明链表是无环的。

三、代码

class Solution {
public:bool hasCycle(ListNode *head) {// 定义快慢指针ListNode* slow = head;ListNode* fast = head;while (fast && fast->next) {slow = slow->next;           // 慢指针走一步fast = fast->next->next;     // 快指针走两步if (slow == fast) {return true;             // 相遇，说明有环}}return false; // fast提前走到链表尾，说明无环}
};