复杂链表的复制

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。（链表前置知识 p = p-next中p指针指向自己的地址，p-next指针指向指针作用域为下一个节点的地址）

示例：
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

两种解法：

1.哈希表，空间和时间都是O(n)

class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) {
            return head;
        }
        //map中存的是(原节点，拷贝节点)的一个映射
        Map<Node, Node> map = new HashMap<>();
        for (Node cur = head; cur != null; cur = cur.next) {
            map.put(cur, new Node(cur.val));
        }
        //将拷贝的新的节点组织成一个链表
        for (Node cur = head; cur != null; cur = cur.next) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
        }

        return map.get(head);
    }
}

2.原地修改，空间复杂度为O(1)

/*
// 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;
        }
       //将拷贝节点放到原节点后面
       for(Node node = head,copy = null; node != null;node = node.next.next){
        copy = new Node(node.val);
        copy.next = node.next;
        node.next = copy;
       }
       //把拷贝节点的random安排上
       for(Node node = head; node != null; node = node.next.next){
           if(node.random != null){
               node.next.random = node.random.next;//将复制节点的随机指针串起来（node.random.next与node.random指向相同）
           }
       }
       //分离拷贝节点和原节点，变成1->2->3和1'->2'->3'两个链表，后者就是答案
        Node newHead = head.next;
        for (Node node = head, temp = null; node != null && node.next != null;) {
            temp = node.next;
            node.next = temp.next;
            node = temp;
        }

        return newHead;
    }
}