142. 环形链表 II

一、题目

142. 环形链表 II

给定一个链表的头节点 head，返回链表开始入环的第一个节点。

如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。

注意：

  • 不允许修改链表。
  • pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

二、题解

思路：快慢指针 / 哈希表。

方法一：快慢指针

1. 核心思路

使用两个指针：

  • slow 每次走一步。
  • fast 每次走两步。

如果链表中有环，那么 slow 和 fast 一定会在环中相遇。

当两个指针相遇后，再让一个指针从 head 出发，另一个指针从相遇点出发。

两个指针每次都走一步，它们最终相遇的位置就是环的入口节点。

2. 具体步骤

  1. 定义两个指针 slow 和 fast，都从 head 出发。
  2. slow 每次走一步，fast 每次走两步。
  3. 如果 fast 走到 null，说明链表无环，返回 null。
  4. 如果 slow == fast，说明链表有环。
  5. 定义两个新指针：
    • index1 从 head 出发。
    • index2 从相遇点出发。
  6. 两个指针每次都走一步。
  7. 当 index1 == index2 时，当前节点就是环的入口节点。

3. 关键逻辑

假设：

  • head 到环入口的距离是 a
  • 环入口到相遇点的距离是 b
  • 相遇点再回到环入口的距离是 c

慢指针走过的距离是：

a + b

快指针走过的距离是：

a + b + n * (b + c)

因为快指针速度是慢指针的 2 倍，所以：

2 * (a + b) = a + b + n * (b + c)

化简可得：

a = (n - 1) * (b + c) + c

这说明：

从 head 走到环入口的距离，等价于从相遇点继续走到环入口的距离。

所以一个指针从 head 出发，另一个指针从相遇点出发，它们最终一定会在环入口相遇。

方法一代码：快慢指针

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        // 1. 处理特殊情况
        if (head == null || head.next == null) {
            return null;
        }

        // 2. 定义快慢指针
        ListNode slow = head;
        ListNode fast = head;

        // 3. 判断链表是否有环
        while (fast != null && fast.next != null) {
            slow = slow.next;        // 慢指针每次走一步
            fast = fast.next.next;   // 快指针每次走两步

            // 如果快慢指针相遇，说明链表中有环
            if (slow == fast) {
                // 4. 寻找环的入口节点
                ListNode index1 = head; // 从头节点出发
                ListNode index2 = slow; // 从相遇点出发

                // 两个指针每次都走一步
                // 再次相遇的位置就是环的入口
                while (index1 != index2) {
                    index1 = index1.next;
                    index2 = index2.next;
                }

                return index1;
            }
        }

        // 5. fast 走到 null，说明链表无环
        return null;
    }
}

复杂度分析

时间复杂度：O(n)O(n)

说明：快慢指针最多遍历链表中的节点有限次，所以时间复杂度是 O(n)O(n)。

空间复杂度：O(1)O(1)

说明：只使用了几个指针变量，没有使用额外的数据结构，所以空间复杂度是 O(1)O(1)。

方法二：哈希表

1. 核心思路

使用 HashSet 记录已经访问过的节点。

从头节点开始遍历链表：

  • 如果当前节点没有出现过，就加入 HashSet。
  • 如果当前节点已经出现过，说明当前节点就是环的入口节点。

因为链表是按照 next 指针一步一步向后走的，所以第一个重复访问到的节点，就是链表开始入环的第一个节点。

2. 具体步骤

  1. 创建一个 HashSet，用来保存访问过的节点。
  2. 定义指针 cur，从 head 开始遍历链表。
  3. 如果 cur 已经存在于 HashSet 中，说明找到了环的入口，返回 cur。
  4. 如果 cur 不存在于 HashSet 中，就把它加入集合。
  5. 继续遍历 cur.next。
  6. 如果最终走到 null，说明链表无环，返回 null。

3. 关键逻辑

关键判断是：

if (visited.contains(cur)) {
    return cur;
}

含义是：

  • 如果当前节点之前已经访问过，说明链表通过环又回到了这个节点。
  • 由于我们是从 head 开始顺序遍历的，所以第一次重复出现的节点就是环的入口节点。

方法二代码：哈希表

import java.util.HashSet;
import java.util.Set;

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        // 1. 定义哈希表，用来记录访问过的节点
        Set<ListNode> visited = new HashSet<>();

        // 2. 定义当前遍历指针
        ListNode cur = head;

        // 3. 遍历链表
        while (cur != null) {
            // 如果当前节点已经访问过，说明这里就是环的入口
            if (visited.contains(cur)) {
                return cur;
            }

            // 记录当前节点
            visited.add(cur);

            // 继续向后遍历
            cur = cur.next;
        }

        // 4. 如果走到 null，说明链表无环
        return null;
    }
}

复杂度分析

时间复杂度：O(n)O(n)

说明：最多遍历链表中的每个节点一次，所以时间复杂度是 O(n)O(n)。

空间复杂度：O(n)O(n)

说明：需要使用 HashSet 保存已经访问过的节点，最坏情况下需要保存所有节点，所以空间复杂度是 O(n)O(n)。

三、两种方法对比

方法时间复杂度空间复杂度特点
快慢指针O(n)O(n)O(1)O(1)不使用额外空间，面试推荐
哈希表O(n)O(n)O(n)O(n)思路简单，容易理解

评论