138 随机链表的复制

一、题目

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

  • val：一个表示 Node.val 的整数。
  • random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为  null 。

你的代码 只 接受原链表的头节点 head 作为传入参数。

二、题解

方法一：哈希表

思路：哈希表。

1. 核心思路

由于链表中每个节点不仅有 next 指针，还有 random 指针。

如果只按照普通链表复制，只能复制 next 关系，无法快速找到 random 指向节点对应的新节点。

所以可以使用哈希表保存：

原节点 -> 复制节点

核心思想是：

  • 第一次遍历：复制每一个节点，并建立原节点和新节点的映射关系；
  • 第二次遍历：根据映射关系，给新节点设置 next 和 random；
  • 最后返回原头节点对应的新头节点。

2. 具体步骤

  1. 如果 head == null，直接返回 null。
  2. 创建一个哈希表 map，用于保存原节点和复制节点的对应关系。
  3. 第一次遍历链表，为每个原节点创建一个新节点。
  4. 第二次遍历链表，为每个新节点设置 next 和 random。
  5. 返回 map.get(head)，也就是复制链表的头节点。

3. 关键逻辑

copyNode.next = map.get(cur.next);
copyNode.random = map.get(cur.random);

解释：

  • cur 是当前原节点；
  • copyNode 是当前原节点对应的复制节点；
  • cur.next 是原节点的下一个节点，所以 map.get(cur.next) 就是复制节点的下一个节点；
  • cur.random 是原节点随机指针指向的节点，所以 map.get(cur.random) 就是复制节点随机指针应该指向的节点；
  • 如果 cur.next 或 cur.random 是 null，那么 map.get(null) 也是 null。

4. 代码

import java.util.HashMap;
import java.util.Map;

class Solution {
    public Node copyRandomList(Node head) {
        // 1. 处理特殊情况
        if (head == null) {
            return null;
        }

        // 2. 定义哈希表：key 是原节点，value 是复制节点
        Map<Node, Node> map = new HashMap<>();

        Node cur = head;

        // 3. 第一次遍历：复制所有节点
        while (cur != null) {
            map.put(cur, new Node(cur.val));
            cur = cur.next;
        }

        cur = head;

        // 4. 第二次遍历：设置复制节点的 next 和 random
        while (cur != null) {
            Node copyNode = map.get(cur);

            copyNode.next = map.get(cur.next);
            copyNode.random = map.get(cur.random);

            cur = cur.next;
        }

        // 5. 返回复制链表的头节点
        return map.get(head);
    }
}

5. 复杂度分析

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

说明：需要遍历链表两次，每次遍历的时间都是 O(n)O(n)。

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

说明：需要使用哈希表保存每个原节点和复制节点的映射关系。

方法二：原地复制

思路：原地修改 / 优化空间。

1. 核心思路

方法一使用了哈希表保存原节点和复制节点的对应关系。

方法二不使用哈希表，而是把复制节点直接插入到原节点后面。

例如原链表是：

A -> B -> C

先复制成：

A -> A' -> B -> B' -> C -> C'

这样每个原节点的复制节点都在它的后面。

因此：

cur.next

就是 cur 的复制节点。

如果：

cur.random = B

那么 cur 的复制节点的 random 应该指向 B'。

而 B' 正好是 B.next。

所以可以通过：

cur.next.random = cur.random.next;

来设置复制节点的随机指针。

这种方法的核心是：

  • 先把复制节点插入到原节点后面；
  • 再利用原节点和复制节点的相邻关系设置 random；
  • 最后把原链表和复制链表拆开。

2. 具体步骤

  1. 如果 head == null，直接返回 null。
  2. 遍历原链表，在每个原节点后面插入一个复制节点。
  3. 再次遍历链表，设置每个复制节点的 random 指针。
  4. 第三次遍历链表，把原链表和复制链表拆分开。
  5. 返回复制链表的头节点。

3. 关键逻辑

if (cur.random != null) {
    cur.next.random = cur.random.next;
}

解释：

  • cur 是当前原节点；
  • cur.next 是当前原节点的复制节点；
  • cur.random 是当前原节点随机指针指向的原节点；
  • cur.random.next 是这个随机节点对应的复制节点；
  • 所以 cur.next.random = cur.random.next 就是让复制节点的 random 指向正确的复制节点。

4. 代码

class Solution {
    public Node copyRandomList(Node head) {
        // 1. 处理特殊情况
        if (head == null) {
            return null;
        }

        Node cur = head;

        // 2. 在每个原节点后面插入复制节点
        while (cur != null) {
            Node copyNode = new Node(cur.val);

            // 复制节点插入到 cur 后面
            copyNode.next = cur.next;
            cur.next = copyNode;

            // 移动到下一个原节点
            cur = copyNode.next;
        }

        cur = head;

        // 3. 设置复制节点的 random 指针
        while (cur != null) {
            if (cur.random != null) {
                // cur.next 是复制节点
                // cur.random.next 是 random 指向节点的复制节点
                cur.next.random = cur.random.next;
            }

            // 跳到下一个原节点
            cur = cur.next.next;
        }

        cur = head;
        Node newHead = head.next;

        // 4. 拆分原链表和复制链表
        while (cur != null) {
            Node copyNode = cur.next;

            // 恢复原链表
            cur.next = copyNode.next;

            // 连接复制链表
            if (copyNode.next != null) {
                copyNode.next = copyNode.next.next;
            }

            // 移动到下一个原节点
            cur = cur.next;
        }

        // 5. 返回复制链表的头节点
        return newHead;
    }
}

5. 复杂度分析

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

说明：需要遍历链表三次，但每次都是线性遍历，所以总时间复杂度是 O(n)O(n)。

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

说明：没有使用额外的哈希表或数组，只使用了几个指针变量。返回的新链表不计入额外空间。

评论