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

LeetCode经典题解：环形链表

news 2026/5/12 10:57:19

在刷 LeetCode 的过程中，“环形链表” 是一道经典的链表类基础题目，这道题核心考察对链表遍历和指针操作的理解，难点在于如何不使用额外空间，高效判断链表是否存在环。今天就来分享这道题的高效解法，严格按照题干思路，通过定义快慢指针，利用“快指针走两步、慢指针走一步”的规则遍历链表，根据指针是否相遇判断是否有环，实现时间复杂度 O(n)、空间复杂度 O(1) 的最优解，完美契合题干要求。

题目描述

给你一个单链表的头节点 head，请你判断该链表中是否有环。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。如果链表中存在环，返回 true；否则，返回 false。要求不使用额外的哈希表、集合等数据结构存储节点，在 O(n) 时间复杂度、O(1) 空间复杂度内完成解题。

补充说明：链表节点仅包含节点值和下一个节点引用；若链表存在环，环可以位于链表的任意位置（表头、中间、末尾），且环的长度无限制。

解题思路

核心思想是快慢指针追及原理：通过定义两个速度不同的指针（快指针、慢指针），同时从链表头节点出发，快指针每次移动两步，慢指针每次移动一步。若链表存在环，两个指针最终会在环内相遇；若链表不存在环，快指针会率先到达链表末尾，循环终止且两指针不会相遇。

具体核心思路（严格贴合题干要求）：

1. 指针初始化：定义快慢指针 fast 和 slow，初始时均指向链表的头节点 head（fast = head，slow = head）。

2. 循环遍历：启动循环，快指针每次走两步，慢指针每次走一步，不断循环遍历链表，循环条件需确保快指针能安全移动（避免空指针异常）。

3. 相遇判断：当快慢指针相遇（fast == slow）时，说明链表存在环，直接返回 true；如果循环结束（快指针到达链表末尾，无法继续移动两步），依然没有相遇，说明链表不存在环，返回 false。

关键说明：若链表存在环，快慢指针进入环后，由于快指针速度是慢指针的两倍，快指针会不断追赶慢指针，最终一定会相遇（不会出现永远追不上的情况）；若有环，循环永远不会因快指针到达末尾而结束，除非两指针相遇，故有环一定会相遇。整个过程仅使用两个指针，不使用额外空间，时间复杂度由遍历次数决定，为 O(n)。

具体步骤

边界判断：若链表为空（head == null）或只有一个节点（head.next == null），则不可能存在环，直接返回 false。
指针初始化：定义快慢指针 fast 和 slow，均赋值为 head（fast = head，slow = head），确保两指针从同一位置出发。
循环遍历与相遇判断：
- 循环条件：fast != null 且 fast.next != null（确保 fast 能安全移动两步，避免 fast.next 为 null 时，fast.next.next 报空指针异常）；
- 每次循环操作：slow 移动一步（slow = slow.next），fast 移动两步（fast = fast.next.next）；
- 每次移动后判断：若 fast == slow（两指针相遇），说明存在环，立即返回 true；
循环结束：若循环因 fast 到达链表末尾而终止（fast == null 或 fast.next == null），说明两指针始终未相遇，链表不存在环，返回 false。

复杂度分析

时间复杂度：O(n)，其中 n 是链表的长度。若链表不存在环，快指针会遍历链表一次（O(n)）后到达末尾，循环终止；若链表存在环，快慢指针会在环内相遇，总遍历次数不超过链表长度（快指针最多比慢指针多走一圈环，总步数仍为 O(n)），因此整体时间复杂度为 O(n)，符合题干要求。

空间复杂度：O(1)，仅使用了 fast 和 slow 两个指针，没有使用哈希表、集合、额外链表等复杂数据结构，完全实现了题干要求的空间优化目标（除必要指针外，无任何额外空间消耗）。

Java 代码

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(fast == slow){ return true; } } return false; } }

代码解析

链表节点定义说明

题目默认链表节点类 ListNode 已定义，包含 val（节点值）和 next（下一个节点引用）两个属性，构造方法用于初始化节点值，next 初始为 null。

初始化与边界判断

边界判断：if (head == null || head.next == null) return false; 空链表没有任何节点，单个节点的 next 为 null，均无法形成环，直接返回 false，避免无效遍历和空指针异常。
ListNode fast = head; ListNode slow = head; 初始化快慢指针，均指向链表头节点，符合题干“初始时均指向 head”的要求，确保两指针从同一位置开始移动。

循环遍历与相遇判断核心逻辑

while (fast != null && fast.next != null)：循环条件是解题的关键，确保 fast 能安全移动两步——若 fast 为 null 或 fast.next 为 null，说明快指针已到达链表末尾，无法继续移动两步，循环终止。

slow = slow.next; 慢指针每次移动一步，严格遵循题干要求。
fast = fast.next.next; 快指针每次移动两步，与慢指针形成速度差，为环内相遇提供条件。
if (fast == slow) return true; 每次移动后立即判断两指针是否相遇，若相遇，说明链表存在环，直接返回 true，无需继续遍历，提升效率。