LeetCode环形链表：快慢指针的教科书级应用，吃透它解决所有循环问题

admin 2026-02-09 阅读:17 评论:0

作为LeetCode的经典双指针问题，LeetCode环形链表快慢指针是Floyd判圈算法（龟兔赛跑算法）的入门载体，涵盖了LeetCode141（检测环）和142（找环入口）两道高频面试题。据鳄鱼java算法课2025年统计，90%的互联...

作为LeetCode的经典双指针问题，LeetCode环形链表快慢指针是Floyd判圈算法（龟兔赛跑算法）的入门载体，涵盖了LeetCode141（检测环）和142（找环入口）两道高频面试题。据鳄鱼java算法课2025年统计，90%的互联网大厂面试会涉及环形链表或其变体问题，而快慢指针解法以O(1)的空间复杂度，成为面试中最被认可的最优解。很多新手第一次做这道题时会用哈希表检测环，但在面试官追问空间优化时会卡壳；而吃透快慢指针的核心逻辑后，不仅能快速写出AC代码，还能推导找环入口的数学原理，甚至将思路迁移到快乐数、数组循环检测等问题中。鳄鱼java学员数据显示，掌握快慢指针解法后，环形链表相关题的平均通过率从40%提升到95%，足见其作为“双指针入门标杆”的核心价值。

题解前置：环形链表的两类问题与核心边界用例

LeetCode环形链表分为两类核心问题：一是LeetCode141“判断链表是否有环”，输入链表头节点，返回是否存在环；二是LeetCode142“环形链表II”，不仅要检测环，还要返回环的入口节点（若无环返回null）。解题前必须覆盖的核心边界用例，是避免提交错误的关键： 1. 空链表：输入null，返回false或null； 2. 单节点无环：输入[1]，返回false或null； 3. 单节点自环：输入[1]且next指向自身，返回true或节点1； 4. 环在链表头部：输入[3,2,0,-4]且-4指向3，返回true或节点3； 5. 环在链表中间：输入[3,2,0,-4]且-4指向2，返回true或节点2。

鳄鱼java算法课导师会反复强调：必须优先测试“自环”和“环在头部”的情况，因为70%的新手快慢指针代码会在这两个场景中出错。

暴力解法的局限：哈希表检测环的优缺点

新手最容易想到的暴力解法是用哈希表存储访问过的节点，遍历链表时若当前节点已在哈希表中，则存在环。Java代码实现如下：

 
public boolean hasCycle(ListNode head) { 
    Set visited = new HashSet<>(); 
    while (head != null) { 
        if (visited.contains(head)) return true; 
        visited.add(head); 
        head = head.next; 
    } 
    return false; 
}

这种解法逻辑直观，时间复杂度为O(n)，但空间复杂度也为O(n)，当链表长度达到10^6时，哈希表会占用大量内存，不符合面试中“空间优化”的核心要求。鳄鱼java学员提交数据显示，用哈希表解法的面试通过率仅为60%，因为面试官通常会追问“能否用O(1)空间实现”，而很多新手无法快速切换到快慢指针思路。

快慢指针的核心逻辑：Floyd判圈算法为什么能检测环？

快慢指针的核心是利用“相对速度差”检测环。具体思路是：初始化两个指针，慢指针（龟）每次走1步，快指针（兔）每次走2步。如果链表无环，快指针会先到达链表尾部（null）；如果链表有环，快慢指针最终会在环内相遇。

数学推导证明了算法的可靠性：假设链表无环部分长度为a，环的长度为b。当慢指针走到环入口时，快指针已经走了2a步，此时快指针在环内的位置为(2a - a) % b = a % b。之后慢指针每走1步，快指针走2步，相对速度为1，即快指针以每步追1的速度靠近慢指针。由于相对速度是1，快指针不会跳过慢指针，最多经过b步后，一定会在环内某个节点相遇。鳄鱼java算法课会用动画演示追及过程，让学员直观理解相对速度的概念，避免死记硬背代码。

LeetCode141实战：环形链表检测的快慢指针实现

Java代码实现如下：

 
public boolean hasCycle(ListNode head) { 
    if (head == null || head.next == null) return false; 
    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; 
}

这里有两种常见的初始值写法：一种是快慢指针都从head出发，另一种是快指针从head.next出发。鳄鱼java导师会强调初始值与循环条件的匹配：若快慢指针都从head出发，循环条件为fast != null && fast.next != null；若快指针从head.next出发，则需要用do-while循环，否则会漏判单节点自环的情况。新手常犯的错误是初始值不统一导致循环条件错误，比如快指针从head.next出发却用前者的循环条件，导致漏判环的存在。

进阶拓展：LeetCode142找环入口的数学推导

LeetCode142要求找到环的入口节点，这是快慢指针的进阶应用，核心是通过数学推导找到“head到入口”与“相遇点到入口”的关系：设慢指针走了s步，快指针走了2s步。慢指针的路径为：无环长度a + 环内k圈 + 相遇点到入口前的距离c（即s = a + k*b + c）；快指针的路径为：无环长度a + 环内m圈 + 相遇点到入口前的距离c（即2s = a + m*b + c）。两式相减得s = (m - k)*b，代入s的表达式得：a + c = (m - 2k)*b，即head到入口的距离a，等于相遇点到入口的距离（环长b - c）加上整数倍环长。因此，将一个指针重置到head，两个指针每次走1步，最终会在环入口相遇。

Java代码实现：

 
public ListNode detectCycle(ListNode head) { 
    if (head == null || head.next == null) return null; 
    ListNode slow = head, fast = head; 
    while (fast != null && fast.next != null) { 
        slow = slow.next; 
        fast = fast.next.next; 
        if (slow == fast) break; 
    } 
    if (fast == null || fast.next == null) return null; 
    fast = head; 
    while (slow != fast) { 
        slow = slow.next; 
        fast = fast.next; 
    } 
    return slow; 
}

鳄鱼java学员常犯的错误是：相遇后未判断是否无环就直接重置指针，导致空指针异常；或者重置指针时错误地将慢指针重置到head，违背数学推导逻辑。

鳄鱼java学员避坑指南：快慢指针的常见错误

根据鳄鱼java学员的实战经验，快慢指针的常见错误有三类： 1. 初始值与循环条件不匹配：快指针从head.next出发，却使用快慢指针都从head出发的循环条件，漏判单节点自环； 2. 循环条件遗漏：只判断fast != null，漏掉fast.next != null，导致快指针为最后一个节点时，执行fast.next.next抛出空指针异常； 3. 数学推导理解模糊：面试中被问“为什么快指针走2步而不是3步”时，无法解释相对速度的概念，只能回答“习惯这么写”，给面试官留下基础不扎实的印象。

鳄鱼java算法课会针对这些错误设计专项练习，比如让学员对比不同初始值的代码，分析循环条件的差异，强化对相对速度和数学推导的理解。