剑指 Offer 35. 复杂链表的复制

本题要求的是复制原链表，所以对于每一个原节点，都需要有一个和它相对应的老节点，从而我们建立一个老节点和新节点的映射关系，old2new，用来存储老节点和新节点的映射关联关系。
先遍历一趟原链表，将所有的节点都创建与之对应的新节点。
再遍历一趟链表时，将每个节点的\(next\)节点和\(random\)节点都从新链表节点中获取。

/*
// 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<Node, Node> old2new = new HashMap<>();
        if(head == null) {
            return null;
        }
        Node p = head;
        while(p != null) {
            old2new.put(p, new Node(p.val));
            p = p.next;
        }
        p = head;
        while(p != null) {
            old2new.get(p).next = old2new.get(p.next);
            old2new.get(p).random = old2new.get(p.random);
            p = p.next;
        }
        return old2new.get(head);
    }
}