138. 随机链表的复制

📝 题目描述

给定一个包含额外 random 指针的链表，random 可指向链表中任意节点或空节点。要求构造该链表的深拷贝：新链表由全新节点组成，其 next 和 random 指针需与原链表对应节点的指针状态一致，且不能指向原链表的节点。

📌 示例

示例 1

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出：[[7,null],[13,0],[11,4],[10,2],[1,0]] 解释：新链表的节点值、next 指向、random 指向均与原链表一致，且所有节点为新创建的对象。

🚀 最优解：原地插入法（三步法）

🔍 思路解析

核心策略：通过三次遍历，在原链表基础上构造新节点，避免使用哈希表存储映射关系：

1. 插入新节点：遍历原链表，在每个原节点后插入对应的新节点（新节点值与原节点相同）；
2. 设置新节点的random指针：再次遍历，若原节点的 random 不为空，新节点的 random 指向原节点 random 的下一个节点（即对应新节点）；
3. 拆分链表：最后遍历，将新节点从原链表中拆分出来，形成独立的新链表。

---

✅ 完整代码（Java）

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;

public class Main {
    private static void printRandomList(Node head) {
        if (head == null) {
            System.out.println(0);
            return;
        }
        List<Node> nodes = new ArrayList<>();
        Node cur = head;
        while (cur != null) {
            nodes.add(cur);
            cur = cur.next;
        }
        Map<Node, Integer> indexMap = new HashMap<>();
        for (int i = 0; i < nodes.size(); i++) {
            indexMap.put(nodes.get(i), i);
        }

        StringBuilder sb = new StringBuilder();
        sb.append(nodes.size()).append("\n");
        for (int i = 0; i < nodes.size(); i++) {
            Node node = nodes.get(i);
            sb.append(node.val).append(" ");
            if (node.random == null) {
                sb.append(-1);
            } else {
                sb.append(indexMap.get(node.random));
            }
            if (i < nodes.size() - 1) {
                sb.append("\n");
            }
        }
        System.out.print(sb.toString());
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        if (!scanner.hasNextInt()) {
            scanner.close();
            return;
        }
        int n = scanner.nextInt();
        Node[] nodes = new Node[n];
        int[] randomIndex = new int[n];

        for (int i = 0; i < n; i++) {
            int val = scanner.nextInt();
            int rand = scanner.nextInt();
            nodes[i] = new Node(val);
            randomIndex[i] = rand;
        }

        for (int i = 0; i < n - 1; i++) {
            nodes[i].next = nodes[i + 1];
        }
        for (int i = 0; i < n; i++) {
            int idx = randomIndex[i];
            if (idx >= 0 && idx < n) {
                nodes[i].random = nodes[idx];
            }
        }

        Node head = n == 0 ? null : nodes[0];
        Solution solution = new Solution();
        Node copied = solution.copyRandomList(head);
        printRandomList(copied);
        scanner.close();
    }
}

class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) return null;

        // 第一步：在原节点后插入新节点（原1→新1→原2→新2...）
        Node cur = head;
        while (cur != null) {
            Node newNode = new Node(cur.val);
            newNode.next = cur.next;
            cur.next = newNode;
            cur = newNode.next;
        }

        // 第二步：设置新节点的random指针
        cur = head;
        while (cur != null) {
            if (cur.random != null) {
                // 原节点random的下一个节点，就是新节点对应的random
                cur.next.random = cur.random.next;
            }
            cur = cur.next.next;
        }

        // 第三步：拆分原链表与新链表
        Node pre = new Node(0);
        Node preCur = pre;
        cur = head;
        while (cur != null) {
            Node temp = cur.next;
            cur.next = temp.next; // 恢复原链表
            preCur.next = temp;   // 连接新节点
            cur = cur.next;
            preCur = temp;
        }
        return pre.next;
    }
}

class Node {
    int val;
    Node next;
    Node random;
    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}

---

🧠 通俗易懂解释

可以把原链表想象成“一串旧珠子”，深拷贝的过程类似给每个旧珠子绑一个新珠子，再把新珠子拆出来串成新链：

1. 绑新珠子：在每个旧珠子后绑一个和它一样的新珠子，形成“旧1→新1→旧2→新2”的链；
2. 复制random指向：旧珠子的random指向哪个旧珠子，对应的新珠子就指向那个旧珠子后的新珠子；
3. 拆新链：把所有新珠子从原链中拆出来，串成独立的新链，同时恢复原链的结构。

以示例1的节点 13（原节点）为例：

1. 插入新节点 13 后，链变为 7→新7→13→新13→...；
2. 原节点 13 的 random 指向原节点 7，则新节点 13 的 random 指向原节点 7 后的新节点 7；
3. 拆分后，新链中 新13 的 random 正确指向 新7。

---

⏱ 时间复杂度

• (O(n))（n 为链表长度） 三次遍历链表，每个节点仅被处理一次。

---

💾 空间复杂度

• (O(1)) 仅使用常数级别的额外空间（无哈希表等存储结构），空间消耗与链表长度无关。