找回密码
 立即注册
首页 业界区 科技 【忍者算法】从公路跑步到链表成环:探索环形链表检测| ...

【忍者算法】从公路跑步到链表成环:探索环形链表检测|LeetCode第141题 环形链表

任娅翠 2025-6-7 13:25:27
从公路跑步到链表成环:探索环形链表检测

生活中的环形

想象两个人在环形跑道上跑步,一个跑得快,一个跑得慢。如果他们一直跑下去,快的跑者一定会从后面追上慢的跑者。这就是我们今天要讨论的环形链表问题的现实映射。在跑道上,两个速度不同的跑者相遇就说明跑道是环形的;同样在链表中,如果两个速度不同的指针相遇,就说明链表中存在环。
问题描述

LeetCode第141题"环形链表"要求:给你一个链表的头节点 head,判断链表中是否有环。如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。
例如:
  1. 输入:3 → 2 → 0 → -4
  2.          ↑___________|
  3. 输出:true
  4. 解释:链表中存在一个环,尾节点连接到第二个节点
  5. 输入:1 → 2
  6.      ↑___|
  7. 输出:true
  8. 解释:链表中存在一个环,尾节点连接到第一个节点
  9. 输入:1 → 2 → 3 → 4
  10. 输出:false
  11. 解释:链表中不存在环
复制代码
简单解法:哈希表记录

最直观的想法是用一个哈希表记录每个走过的节点。就像在跑道上撒面包屑,如果遇到已经撒过面包屑的地方,说明路径形成了环。
哈希表解法实现
  1. public boolean hasCycle(ListNode head) {
  2.     Set<ListNode> seen = new HashSet<>();
  3.    
  4.     while (head != null) {
  5.         // 如果已经见过这个节点,说明有环
  6.         if (seen.contains(head)) {
  7.             return true;
  8.         }
  9.         // 记录当前节点
  10.         seen.add(head);
  11.         head = head.next;
  12.     }
  13.    
  14.     return false;
  15. }
复制代码
优化解法:快慢指针(Floyd判圈算法)

这个经典算法也被称为"龟兔赛跑算法",就像我们开始说的跑步场景:让一快一慢两个指针在链表上移动,如果存在环,快指针最终一定会追上慢指针。
为什么快慢指针一定会相遇?

想象在环形跑道上:

  • 快指针每次走2步,慢指针每次走1步
  • 相对来说,快指针每次都在追赶慢指针1步
  • 如果有环,这就像在操场上追赶,快指针一定会追上慢指针
  • 如果无环,快指针会先到达终点
代码实现与详解
  1. public boolean hasCycle(ListNode head) {
  2.     if (head == null || head.next == null) {
  3.         return false;
  4.     }
  5.    
  6.     // 初始化快慢指针
  7.     ListNode slow = head;
  8.     ListNode fast = head;
  9.    
  10.     // 快指针每次走两步,慢指针每次走一步
  11.     while (fast != null && fast.next != null) {
  12.         slow = slow.next;          // 慢指针走一步
  13.         fast = fast.next.next;     // 快指针走两步
  14.         
  15.         // 如果两个指针相遇,说明有环
  16.         if (slow == fast) {
  17.             return true;
  18.         }
  19.     }
  20.    
  21.     // 如果快指针到达链表末尾,说明无环
  22.     return false;
  23. }
复制代码
图解过程

以一个有环链表为例:
  1. 1) 初始状态:
  2. 3 → 2 → 0 → 4
  3.     ↑_________|
  4. S,F
  5. (S=slow, F=fast)
  6. 2) 第一次移动后:
  7. 3 → 2 → 0 → 4
  8.     ↑_________|
  9.     S   F
  10. 3) 第二次移动后:
  11. 3 → 2 → 0 → 4
  12.     ↑_________|
  13.         S   F
  14. 4) 最终相遇:
  15. 3 → 2 → 0 → 4
  16.     ↑_________|
  17.         S,F
复制代码
复杂度比较

哈希表解法:

  • 时间复杂度:O(n)
  • 空间复杂度:O(n),需要存储已访问节点
  • 优点:思路直观,容易实现
  • 缺点:需要额外空间
快慢指针解法:

  • 时间复杂度:O(n)
  • 空间复杂度:O(1),只需要两个指针
  • 优点:空间效率高,实现优雅
  • 缺点:需要理解快慢指针的数学原理
核心原理解析

1. 数学证明

为什么快慢指针一定会相遇?

  • 假设环长为K,入环前长度为N
  • 慢指针走S步时,快指针走2S步
  • 快指针多走的S步一定是环长K的整数倍
  • 因此快慢指针一定会在入环后的K-N步内相遇
2. 临界情况分析


  • 空链表
  • 单节点链表
  • 环的长度为1(自环)
  • 入环点在开头或结尾
实用技巧总结

解决环形问题的关键点:

  • 掌握快慢指针技巧
  • 理解环形结构的特性
  • 考虑边界情况
  • 注意指针移动的顺序
相关的环形问题:

  • 找到环的入口点
  • 计算环的长度
  • 找到环中的特定节点
小结

环形链表的检测问题是链表操作中的一个经典问题。它教会我们:

  • 如何用最小的空间解决复杂问题
  • 快慢指针这个强大的算法技巧
  • 如何将现实问题映射到算法思维
  • 优雅解法往往来自于深刻的数学原理
建议:多思考快慢指针的应用场景,它不仅用于检测环,还可以:

  • 找到链表中点
  • 判断链表是否为回文
  • 找到倒数第K个节点
这些问题都可以用类似的思维方式来解决!
作者:忍者算法
公众号:忍者算法
我准备了一份刷题清单,以及这些题目的详细题解,覆盖了绝大部分常见面试题。我可以很负责任地说,只要你把这些题真正掌握了,80%的算法面试都能遇到相似题目。公众号回复【刷题清单】获取~

来源:程序园用户自行投稿发布,如果侵权,请联系站长删除
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!
您需要登录后才可以回帖 登录 | 立即注册