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

题目描述

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

要求返回这个链表的深拷贝。

示例：

输入: {"$id":"1","next":{"$id":"2","next":null,"random":{"$ref":"2"},"val":2},"random":{"$ref":"2"},"val":1}

思路

1. 对要拷贝的链表进行两次遍历。

2.第一次遍历以原链表节点为key，新建节点为value将它们存储再哈希表中。

3.第二次遍历将新建的节点取出，并设置next和random节点。

Java代码实现

    public Node copyRandomList(Node head) {
        Map<Node,Node> nodeMap = new HashMap();

        Node p = head;

        while(p != null){
            nodeMap.put(p,new Node(p.val));
            p = p.next;
        }

        p = head;

        while(p != null){
            nodeMap.get(p).next = nodeMap.get(p.next);
            nodeMap.get(p).random = nodeMap.get(p.random);
            p = p.next;
        }

        return nodeMap.get(head);
    }