给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。

傷城~ 2022-10-28 10:13 30阅读 0赞

## 题目要求 ##

给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。要求返回这个链表的 深拷贝。

我们用一个由 n 个节点组成的链表来表示输入/输出中的链表。  
每个节点用一个 \[val, random\_index\] 表示：  
val：一个表示 Node.val 的整数。  
random\_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。

## 代码 ##

class Node {
        
        int val;
        Node next;
        Node random;
    
        public Node(int val) {
        
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
    
    public class TestDemoSet {
        
        public Node copyRandomList(Node head) {
        
            //1.遍历旧链表，把旧链表这里的每个节点一次插入到map中，key是旧节点，value是新的节点
            Map<Node,Node> map = new HashMap<>();
            for (Node cur = head; cur!= null; cur = cur.next){
        
                map.put(cur,new Node(cur.val));
            }
            //2.再次遍历链表，修改新链表节点中的next和random
            for (Node cur = head; cur!= null; cur = cur.next){
        
                //先从map中找到cur对应的新链表节点
                Node newCur = map.get(cur);
                newCur.next = map.get(cur.next);
                newCur.random = map.get(cur.random);
            }
            //需要返回新链表的头节点
            return map.get(head);
    
        }
    }