《力扣刷题计划》复制带随机指针的链表

深藏阁楼爱情的钟 2024-04-23 15:35 63阅读 0赞

![06292fe942334609bf0405b73199cbc2.png][]

**?每一个结点有三个属性：**

![d991acc403164fc28f5a66d95cc950cd.png][]

**?链表的样子大概是这样：**

![fed92f9e6eae9293eecae9300b2e44b0.png][]

注意这里我们复制的结点是引用类型，即我们复制的不只是结点的地址，我们需要复制的是旧结点。

比如一个这样的原链表

![64da92dd8f4545d89bf103b1f15266df.png][]

我们的复制不是又生成一个和上面一模一样的链表出来，**我们复制的是有着原来链表结构的新的链表**

**新的链表的每个结点所对应的值可能和原来链表的值相同，但next和random的肯定是不同的（但所对应的关系是相同的）**

![215b9987da3f4dbeb806ba64d8d60fc5.png][]

为了在新链表中持和原来链表中各个结点的对应关系，我们需要用Map来记录

比如上图中

![b71f9496c0204e59b908fd6e13bcb63e.png][]

代码展示：

/*
    // 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) {
            if (head == null) {
                return null;
            }
            Node cur = head;
            Map<Node, Node> map = new HashMap<>(); // 如果用TreeMap里面放的元素一定是可比较的,只能用HashMap
            // 构建新旧结点的键值对关系，旧结点是Key,新结点是Value
            while (cur != null) {
                Node tmp = new Node(cur.val); // 构造新结点tmp,旧结点是cur
                map.put(cur, tmp);
                cur = cur.next;
            }
            cur = head;
            // 按旧链表的结点对应关系构建新的结点，注意我们是深拷贝——即非引用类型可以直接把值拷贝出来，但对于引用类型我们拷贝的不只是地址值，还有该引用所对应的结点
            while(cur != null) {
                map.get(cur).next = map.get(cur.next);
                map.get(cur).random = map.get(cur.random);
                cur = cur.next;
            }
            return map.get(head); // 我们要返回的是新结点的head---及key(head) 所对应的 value值是map.get(head)
        }
    }

[06292fe942334609bf0405b73199cbc2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/46fcd8f1b2ec4923a30d143243070c16.png
[d991acc403164fc28f5a66d95cc950cd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/1cbdd1ccfb6645738847ea2400ed7a85.png
[fed92f9e6eae9293eecae9300b2e44b0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/f5b0ea10f8174bd787b40634b4875a00.png
[64da92dd8f4545d89bf103b1f15266df.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/bdcdee95fd9a4604a88c9d43a03a1b14.png
[215b9987da3f4dbeb806ba64d8d60fc5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/566436b4f2de4f419e212afc6b53113d.png
[b71f9496c0204e59b908fd6e13bcb63e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/77a1cc67c84c4eada088b55ea26406c8.png