Skip to content

138. 随机链表的复制：（迭代、递归）两次访问和哈希表 与 节点拆分 两种解决思路.md

Latest commit

 

History

History
188 lines (144 loc) · 8.97 KB

138. 随机链表的复制：（迭代、递归）两次访问和哈希表 与 节点拆分 两种解决思路.md

File metadata and controls

188 lines (144 loc) · 8.97 KB
Raw

题目简述：

给你一个长度为 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 作为传入参数。

题目链接：138. 随机链表的复制

方案一：两次顺序遍历，利用哈希表

迭代遍历实现

思路

该方案是最直观、直接的方案，时间复杂度为 $O(N)$、空间复杂度为 $O(N)$，需要进行两次遍历。

具体而言，

  1. 在第一次遍历时我们复制节点 random 字段除外的字段。也就是说，在这一次遍历中针对旧链表的一个节点，我们新建一个相应的节点作为复制节点，但该节点仅复制可控的 val 字段与 next 字段，暂不处理 random 字段——因为此时新链表的节点尚未完全创建，当前复制节点的 random 有可能指向一个尚未创建的新链表节点，我们怎么能试图赋值一个不存在的东西呢？

    但为了下一次遍历时我们能完成新链表 random 字段的赋值、使新链表成为合法的赋值链表，在这一次遍历中我们需要一个哈希表，该哈希表存储旧链表节点到相应新链表节点的映射关系。该映射的存储在每次遍历的新建节点中同时进行。

  2. 在第二次遍历中我们就要根据哈希表中的映射填充新链表的 random 字段了。整个第二次遍历都是为了 random 字段的填充。

    由于此时新链表的节点已经全部创建完成了，因此哈希表中存储了全部旧节点到相应新节点的映射，我们在遍历时将旧节点的 random 字段作为哈希映射的 key 并将得到的 value 作为新节点的 random 值即可。

更多的细节参见代码中的注释。

代码

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

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

class Solution {
    public Node copyRandomList(Node head) {
        HashMap<Node, Node> map = new HashMap<>();
        // 添加新旧链表的哨兵节点，避免单独处理头节点的复制
        Node oldVirtualHead = new Node(0);
        oldVirtualHead.next = head;
        Node newVirtualHead = new Node(0);

        // 第一次遍历：新建链表并复制填充 val 与 next，同时存储旧链表与新链表节点地址的映射关系
        Node node = oldVirtualHead;
        Node newNode = newVirtualHead;
        while (node.next != null) {
            Node tmp = new Node(node.next.val);
            newNode.next = tmp;
            // 旧节点地址 -> 新节点地址
            map.put(node.next, tmp);
            node = node.next;
            newNode = newNode.next;
        }

        // 第二次遍历：根据映射关系，填充新链表的 random 字段
        node = oldVirtualHead;
        newNode = newVirtualHead;
        while (node.next != null) {
            newNode.next.random = map.get(node.next.random);
            node = node.next;
            newNode = newNode.next;
        }

        return newVirtualHead.next;
    }
}

递归遍历实现

查看了官方题解，发现官方题解异常简洁，即使官方题解的一个方法也使用了哈希表：

class Solution {
    Map<Node, Node> cachedNode = new HashMap<Node, Node>();

    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        if (!cachedNode.containsKey(head)) {
            Node headNew = new Node(head.val);
            cachedNode.put(head, headNew);
            headNew.next = copyRandomList(head.next);
            headNew.random = copyRandomList(head.random);
        }
        return cachedNode.get(head);
    }
}

分析官方题解的代码，发现其哈希表用法与我们此前的实现一模一样，map 与 cachedNode 实际上均存储原节点到相应新节点的映射关系，但官方题解巧妙利用了递归，这使得算法可以在递归中对新节点 next 与 random 字段“一视同仁”地赋值递归调用（而不是显式的两次遍历）的同时拥有十分简洁的代码实现。

可以说，我们此前的实现与该实现是完全相同的思想，二者具有相同的时空复杂度，只不过一个是迭代实现，一个是递归实现，因此我没有修改大标题“两次顺序遍历”，因为递归实际上只是隐含了两次访问的过程。当然两种实现在细节上还是存在一些不同的：

  • 迭代实现严格遵循先新建链表再填充 random 的顺序，两次遍历具有明确的边界和顺序关系；
  • 递归实现对 random 字段处理的时机不同于迭代，递归实现通过递归调用混合处理了 next 与 random，同一个节点的 random 字段有可能比 next 更早被访问、处理，但哈希表的性质保证了不重不漏（这也是 if (!cachedNode.containsKey(head)) 的作用）。

递归的实现在链表很长时可能有栈溢出的风险，但经测试，截止至 2025 年 7 月 14 日，递归实现的算法可以通过力扣的所有测试用例。

方案二：节点拆分

思路

这一解法是我查看他人的题解时学习到的，所实现的算法性能比方案一的算法更优，时间复杂度为 $O(N)$，空间复杂度仅为 $O(1)$（不考虑返回的新链表的空间开销，即常数级的额外空间开销，或称链表的原地操作）。归根结底该方案的优越性体现在巧妙地处理了 random，毕竟如果没有 random 字段那么一次顺序遍历直接就能完成复制了。

我们先看看该方案的操作流程，假设我们有链表 ${A,B,C}$，链表的序关系为 $A\to B\to C$，那么

  1. 首先依次复制旧节点，将新节点插入到相应旧节点的后面，例如设节点 $A$ 复制得到的新节点为 $A'$、节点 $B$ 复制得到的新节点为 $B'$、节点 $C$ 复制得到的新节点为 $C'$，则复制完成后的混合新旧节点的链表为 $A\to A'\to B\to B'\to C\to C'$。

    在这一步暂时不考虑新节点的 random 字段，总结我们的行为：

    • 针对每个旧节点，新建相应的新节点；
    • 此时新节点与相应的旧节点具有相同的 val 与 next；
    • 修改旧节点的 next，使其指向相应的新节点；
    • 不修改其他字段，复制时暂不考虑新节点的 random。

  2. 这时我们可以发现新节点的 random 字段事实上就等于其相应旧节点 random 字段所指向对象的 next 字段。那么再遍历一次以更新新节点的 random 字段即可。例如，$A'$ 的 random 值就等于 $A$ 的 random 所指向对象——假设为 $C$，那么 $C$ 当下的 next 指向其复制节点 $C'$，因此将 $C'$ 的地址或引用赋予 $A'$ 的 random 字段即可。

  3. 最后需要将混合新旧节点的链表分离开来，复原出原链表并得到新复制的链表。这一步只需要区分奇偶节点并相应修改 next 字段即可。

理解了该算法的操作流程，也就能看出该算法设计的精妙之处，无需多言。

代码

class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        
        // 1. 复制节点
        Node cur = head;
        while (cur != null) {
            Node tmp = cur.next;
            cur.next = new Node(cur.val);
            cur.next.next = tmp;
            cur = tmp;
        }

        // 2. 赋值新节点 random 字段
        cur = head;
        while (cur != null) {
            if (cur.random != null) {
                cur.next.random = cur.random.next; 
            }
            cur = cur.next.next;
        }

        // 3. 分离混合链表（修改节点 next 字段）
        Node newHead = head.next;
        cur = head;
        while (cur != null) {
            Node newNode = cur.next;
            cur.next = newNode.next;
            cur = newNode.next;
            newNode.next = cur == null? null : cur.next;
        }

        return newHead;
    }
}