专栏名称: FanZhe、FanZhe

Leetcode第五天之复制带随机指针的链表（138）

FanZhe、FanZhe · CSDN · · 2020-11-09 08:15

正文

在这里插入图片描述

新建Node实体类

public class Node {
    int val;
    Node next;
    Node random;

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

哈希表

    public static Node copyRandomList(Node head) {
                if (head==null)
            return null;
        //哈希表中，key是原来的节点，value是现在的
        Map<Node,Node> hashMap=new HashMap<>();
        Node p=head;
        //将原节点放入哈希表中
        while (p!=null){
            Node newNode=new Node(p.val);
            hashMap.put(p,newNode);
            p=p.next;
        }
        p=head;
        //遍历原链表，设置新节点的next和random
        while (p!=null){
            //p是原节点，get(p)就是新的节点
            Node newNode=hashMap.get(p);
            if(p.next!=null){
                newNode.next=hashMap.get(p.next);
            }
            //p.random表示原节点随机指向
            //hashMap中：
            // hashMap.get(p.random)表示hashMap.get(p)对应的新节点
            if (p.random!=null){
                newNode.random=hashMap.get(p.random);
            }
            p=p.next;
        }
        //返回原节点对应的新节点
        return hashMap.get(head);
    }