图解LeetCode——141. 环形链表

判断链表是否有环可以通过哈希集合存储遍历节点或快慢指针两种方法实现。

一、方法一：哈希集合存储遍历节点

核心思路：通过遍历链表，将每个节点存入哈希集合中。若在遍历过程中发现当前节点已存在于集合中，则说明链表有环；若遍历到链表末尾（next为null），则说明无环。
具体步骤：
初始化一个空的哈希集合Set<ListNode>。
从链表头节点head开始遍历：
若当前节点不在集合中，将其加入集合。
若当前节点已在集合中，返回true（有环）。
若当前节点为null，返回false（无环）。
继续遍历下一个节点，直到链表结束。
示例分析：
示例1：链表3→2→0→-4→2（环连接至第二个节点）。
遍历过程：3（加入集合）→2（加入集合）→0（加入集合）→-4（加入集合）→再次遇到2（已存在），返回true。
示例2：链表1→2→1（环连接至第一个节点）。
遍历过程：1（加入集合）→2（加入集合）→再次遇到1（已存在），返回true。
示例3：链表1→null（无环）。
遍历过程：1（加入集合）→next为null，返回false。
代码实现：

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

二、方法二：快慢指针法

核心思路：使用两个指针，慢指针每次移动1步，快指针每次移动2步。若链表有环，快指针最终会追上慢指针；若无环，快指针会先到达链表末尾。
具体步骤：
初始化慢指针slow指向头节点head，快指针fast指向head.next（若head为null则直接返回false）。
循环移动指针：
若slow与fast相遇，返回true（有环）。
更新slow为slow.next。
更新fast为fast.next.next（需先检查fast和fast.next是否为null）。
若循环结束（fast为null），返回false（无环）。
示例分析：
示例1：链表3→2→0→-4→2（环连接至第二个节点）。
初始状态：slow=3，fast=2。
移动过程：
第1步：slow=2，fast=0。
第2步：slow=0，fast=2。
第3步：slow=-4，fast=0。
第4步：slow=2，fast=2（相遇），返回true。
示例2：链表1→2→1（环连接至第一个节点）。
初始状态：slow=1，fast=2。
移动过程：
第1步：slow=2，fast=1。
第2步：slow=1，fast=1（相遇），返回true。
示例3：链表1→null（无环）。
初始状态：slow=1，fast=null。
直接返回false。
代码实现：

public class Solution { public boolean hasCycle(ListNode head) { if (head == null) { return false; } ListNode slow = head; ListNode fast = head.next; while (fast != null && fast.next != null) { if (slow == fast) { return true; } slow = slow.next; fast = fast.next.next; } return false; }}

三、方法对比

哈希集合法：
时间复杂度：O(n)，需遍历链表一次。
空间复杂度：O(n)，需存储所有节点。
快慢指针法：
时间复杂度：O(n)，快指针最多移动两倍于慢指针的步数。
空间复杂度：O(1)，仅需两个指针的额外空间。

推荐使用快慢指针法，因其空间效率更高，尤其适用于大规模链表。

您可能感兴趣问答

Collapsible

热门标签

热点问答