数据结构Map 的算法——随机链的复制

Han.miracle

发布于 2025-12-22 15:00:07

950

文章被收录于专栏：Java核心技术图谱：原理·对比·避坑Java核心技术图谱：原理·对比·避坑

地址：https://leetcode.cn/problems/copy-list-with-random-pointer/description/ 给你一个长度为 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 作为传入参数。

cur 代表的是整个节点对象，它包含节点的所有属性，包括 val（值）、next 指针（指向后继节点）、random 指针（如果是带随机指针的链表）等

第一种方法：Map 步骤 1：创建复制节点并建立映射遍历原链表，对每个原节点 cur，创建一个值相同的新节点 node。将原节点 cur 和复制节点 node 存入哈希表 map 中，形成原节点→复制节点的映射。步骤 2：构建复制链表的指针关系再次遍历原链表，对于每个原节点 cur：复制节点的 next 指针：通过哈希表获取原节点 cur.next 对应的复制节点，赋值给当前复制节点的 next。复制节点的 random 指针：通过哈希表获取原节点 cur.random 对应的复制节点，赋值给当前复制节点的 random。

class Solution {
    public Node copyRandomList(Node head) {
        // 哈希表：原节点 → 复制节点
        HashMap<Node, Node> map = new HashMap<>();
        
        // 第一步：创建所有复制节点并建立映射
        Node cur = head;
        while (cur != null) {
            Node copyNode = new Node(cur.val); // 复制节点值
            map.put(cur, copyNode); // 存储原节点与复制节点的映射
            cur = cur.next;
        }
        
        // 第二步：构建复制节点的 next 和 random 指针
        cur = head;
        while (cur != null) {
            // 复制节点的 next 指向原节点 next 对应的复制节点
            map.get(cur).next = map.get(cur.next);
            // 复制节点的 random 指向原节点 random 对应的复制节点
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        
        // 返回复制链表的头节点（原链表头节点对应的复制节点）
        return map.get(head);
    }
}

第二种方法:链表代码分步解析步骤 1：在原节点后插入复制节点遍历原链表，为每个节点 cur 创建复制节点 copy，并将 copy 插入到 cur 和 cur.next 之间。

while (cur != null) {
    Node copy = new Node(cur.val); // 复制当前节点值
    copy.next = cur.next;         // 复制节点的next指向原节点的next
    cur.next = copy;              // 原节点的next指向复制节点
    cur = copy.next;              // 移动到下一个原节点（跳过复制节点）
}

步骤 2：设置复制节点的 random 指针再次遍历，利用原节点的 random 指针定位复制节点的 random：若原节点 cur.random = X，则复制节点 copy.random 应为 X 的复制节点 X’（即 X.next）。

while (cur != null) {
    Node copy = cur.next;
    if (cur.random != null) {
        copy.random = cur.random.next; // 复制节点的random指向原random的复制节点
    }
    cur = copy.next; // 移动到下一个原节点
}

步骤 3：拆分原链表和复制链表最后遍历，将原节点和复制节点分离：恢复原链表：cur.next 跳过复制节点，指向原本的下一个原节点。构建复制链表：将复制节点依次连接到 copyHead 后

while (cur != null) {
    Node copy = cur.next;
    cur.next = copy.next;       // 恢复原链表指针
    copyCur.next = copy;        // 连接复制节点到复制链表
    cur = cur.next;             // 移动原链表指针
    copyCur = copyCur.next;     // 移动复制链表指针
}

class Solution {
    public Node copyRandomList(Node head) {
        // 边界条件：空链表直接返回null
        if (head == null) {
            return null;
        }

        // 步骤1：在原节点后插入复制节点
        Node cur = head;
        while (cur != null) {
            Node copy = new Node(cur.val);
            copy.next = cur.next;
            cur.next = copy;
            cur = copy.next;
        }

        // 步骤2：设置复制节点的random
        cur = head;
        while (cur != null) {
            Node copy = cur.next;
            if (cur.random != null) {
                copy.random = cur.random.next;
            }
            cur = copy.next;
        }

        // 步骤3：拆分原链表和复制链表
        cur = head;
        Node copyHead = new Node(0);
        Node copyCur = copyHead;
        while (cur != null) {
            Node copy = cur.next;
            // 恢复原链表
            cur.next = copy.next;
            // 构建复制链表
            copyCur.next = copy;
            // 移动指针
            cur = cur.next;
            copyCur = copyCur.next;
        }

        return copyHead.next;
    }

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-10-29，如有侵权请联系 cloudcommunity@tencent.com 删除

链表