🌕 138. 复制带随机指针的链表

难度: 🌕

问题描述

---

解法

/*
// 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) {
        // 思路：
        // 链表的深拷贝 - 通过 map 存放源节点 & 拷贝节点
        // 按照 next 顺序，依次拷贝节点，在拷贝 random 的过程中，如果 random 节点还未拷贝，进行拷贝
        // 类似题目 - 133 图的深拷贝
        return mySol(head);
    }

    private Node mySol(Node head) {
        HashMap<Node, Node> map = new HashMap<>();
        Node cur = head;
        while(cur != null) {
            Node cl;
            if(map.containsKey(cur)) {
                cl = map.get(cur); // 直接取出已经完成拷贝的节点
            } else {
                cl = new Node(cur.val); // 创建新节点
                map.put(cur, cl); // 无需等到 random 节点的拷贝完成
            }
            // 进行 next 节点 & random 节点的连接
            if(cur.next != null) {
                Node next = cur.next;
                if(map.containsKey(next)) {
                    cl.next = map.get(next);
                } else {
                    Node tmp = new Node(next.val); // 创建
                    map.put(next, tmp);
                    cl.next = tmp;
                }
            }
            if(cur.random != null) {
                Node rand = cur.random;
                if(map.containsKey(rand)) {
                    cl.random = map.get(rand);
                } else {
                    Node tmp = new Node(rand.val);
                    map.put(rand, tmp);
                    cl.random = tmp;
                }
            }
            // cur 的深拷贝节点完成，继续下一个节点
            cur = cur.next;
        }   
        return map.get(head);     
    }
}

---

输出