链表判环 寻找环入口 两种解法详解

前言链表环问题是链表经典高频面试题分为两个基础题型hasCycle判断单链表中是否存在环detectCycle若链表有环返回环的起始节点无环返回null。单链表单向遍历无法直接回头判断重复节点业界主流两种解法哈希集合法直观易写、快慢指针弗洛伊德判圈算法空间最优面试核心考点。统一链表节点定义class ListNode { int val; ListNode next; ListNode(int x) { val x; next null; } }一、哈希集合解法判环 找环起点通用核心思路利用HashSet存储已经遍历过的节点对象注意存节点引用不是节点值不同节点允许值相同遍历链表指针依次向后移动每一步先判断当前节点是否在集合中存在链表有环当前节点就是环入口不存在将当前节点存入集合指针后移指针走到null说明链表无环。优缺点优点逻辑极简无需数学推导判环、找环入口代码几乎一致上手零门槛缺点需要额外哈希集合存储所有节点空间复杂度O(n)。1. 判断链表是否有环 hasCyclepublic class Solution { public boolean hasCycle(ListNode head) { SetListNode set new HashSet(); ListNode p head; while (p ! null) { // 当前节点已访问过存在环 if (set.contains(p)) { return true; } set.add(p); p p.next; } // 遍历到末尾无环 return false; } }2. 找到环的起始节点 detectCyclepublic class Solution { public ListNode detectCycle(ListNode head) { SetListNode set new HashSet(); ListNode p head; while (p ! null) { // 重复节点即为环入口直接返回 if (set.contains(p)) { return p; } set.add(p); p p.next; } // 无环返回null return null; } }二、快慢指针弗洛伊德判圈算法空间 O (1) 最优解1. 快慢指针判断是否存在环 hasCycle核心思路快慢指针模拟跑道追及问题慢指针slow每次走 1 步快指针fast每次走 2 步若无环快指针会率先走到链表末尾null循环终止返回false若存在环快慢指针一定会在环内某处相遇相遇即证明有环。边界提前特判链表为空 / 只有单个节点直接无环。优缺点优点仅两个临时指针空间复杂度O(1)时间O(n)面试最优解法缺点需要理解追及逻辑无法直接得到环入口找起点需要额外推导。完整代码public class Solution { 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 (fast slow) { return true; } } // 快指针走到链表尾部无环 return false; } }补充快慢指针寻找环入口拓展考点数学推导核心结论快慢指针第一次相遇后将慢指针重置到链表头快慢指针同时改为每次走 1 步二者再次相遇的节点就是环的起始节点。推导本质头部到环入口距离 相遇点到环入口的剩余环长。detectCycle 快慢指针完整代码public class Solution { public ListNode detectCycle(ListNode head) { ListNode slow head; ListNode fast head; // 第一步快慢指针找相遇点 while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; // 两指针相遇 if (slow fast) { // 慢指针放回头部 slow head; // 同步一步走相遇即为环起点 while (slow ! fast) { slow slow.next; fast fast.next; } return slow; } } // 无环 return null; } }三、两种解法综合对比方案时间复杂度空间复杂度优势短板哈希集合O(n)O(n)逻辑简单可直接返回环入口占用额外内存长链表开销大快慢指针O(n)O(1)常数空间性能最优需要数学推导找入口多一轮遍历四、面试核心考点总结哈希表注意点存入节点引用而非数值多个节点值相同但地址不同不算环快慢指针边界循环条件必须是fast ! null fast.next ! null防止fast.next.next空指针报错判环 vs 找入口区分只判断有无环快慢指针相遇直接返回true寻找环起点相遇后慢指针归头同速前进二次相遇才是入口场景选择刷题快速写答案用哈希正式面试、追求最优空间复杂度必须掌握快慢指针弗洛伊德算法。