LeetCode LCR 022. 环形链表 II

Categories:

题目描述
思路分析
1. 解法一：Floyd 判环 + 数学推导（推荐）
2. 解法二：哈希表（可选）
相似题目

题目描述

✅ LCR 022. 环形链表 II

思路分析

解法一：Floyd 判环 + 数学推导（推荐）

核心思路：

第一阶段：找相遇点：slow 走 1 步，fast 走 2 步。设链表头到环入口距离为 a，环入口到相遇点距离为 b，相遇点到环入口距离为 c（环长 = b + c）。

数学推导：相遇时 fast 路程是 slow 的 2 倍：2(a+b) = a + b + n(b+c)，化简得 a = (n-1)(b+c) + c。即从头到环入口的距离等于从相遇点再走 c 步（加若干整圈）到环入口的距离。

第二阶段：定位入口：令一个指针从头节点出发，另一个从相遇点出发，两者每次走 1 步，第二次相遇即为环的入口节点。

复杂度分析：

时间复杂度：O(n)，其中 n 表示链表的节点数。

空间复杂度：O(1)，只使用了常数级别的额外空间。

public class Solution {
    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) {
                // 第二阶段：slow 回到 head，两指针同步前进找环入口
                slow = head;
                while (slow != fast) {
                    slow = slow.next;
                    fast = fast.next;
                }
                return slow;
            }
        }

        return null;
    }
}

func detectCycle(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return nil
    }

    slow, fast := head, head
    // 第一阶段：快慢指针找相遇点
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next

        if slow == fast {
            // 第二阶段：entry 从头出发，slow 留在相遇点，同步前进找环入口
            entry := head
            for entry != slow {
                entry = entry.Next
                slow = slow.Next
            }
            return entry
        }
    }

    return nil
}

解法二：哈希表（可选）

核心思路：

遍历链表，将每个节点存入哈希集合。

若当前节点已在集合中，则该节点即为环的入口；若遍历结束未找到重复节点，则链表无环。

复杂度分析：

时间复杂度：O(n)，其中 n 表示链表的节点数，每个节点最多访问一次。

空间复杂度：O(n)，其中 n 表示链表的节点数，哈希集合最多存储 n 个节点。

public class Solution {
    public ListNode detectCycle(ListNode head) {
        // 使用哈希集合记录已访问的节点
        Set<ListNode> visited = new HashSet<>();
        ListNode cur = head;
        while (cur != null) {
            // 若节点已存在于集合中，则为环的入口
            if (visited.contains(cur)) {
                return cur;
            }
            visited.add(cur);
            cur = cur.next;
        }
        return null;
    }
}

func detectCycle(head *ListNode) *ListNode {
    // 使用哈希集合记录已访问的节点
    visited := make(map[*ListNode]bool)
    cur := head
    for cur != nil {
        // 若节点已存在于集合中，则为环的入口
        if visited[cur] {
            return cur
        }
        visited[cur] = true
        cur = cur.Next
    }
    return nil
}

相似题目

题目	难度	考察点
141. 环形链表	简单	快慢指针
287. 寻找重复数	中等	快慢指针、Floyd 判环
160. 相交链表	简单	双指针
876. 链表的中间结点	简单	快慢指针
202. 快乐数	简单	快慢指针、哈希表
457. 环形数组中是否存在循环	中等	快慢指针
19. 删除链表的倒数第 N 个结点	中等	快慢指针
234. 回文链表	简单	快慢指针、反转链表
143. 重排链表	中等	快慢指针、反转链表

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/71579853