[数据结构与算法]复杂链表的复制（额外带一个random）

方法一：
利用图存储每一个节点的属性，键为原链表，值为新链表，先遍历一边链表，依据原链表生成新节点，再遍历一边链表，在图中用原节点取出新节点并且依据原节点关系给新节点赋予next和random关系。

public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        Map<Node, Node> vals = new HashMap<>();
        Node cur = head;
        while (cur != null) {
            vals.put(cur, new Node(cur.val));
            cur = cur.next;
        }
        cur = head;
        while (cur != null) {
            vals.get(cur).next = vals.get(cur.next);
            vals.get(cur).random = vals.get(cur.random);
            cur = cur.next;
        }

        return vals.get(head);
    }

方法二：
组建一个新链表，该链表由一个原节点->该节点的一个复制->第二个原节点->第二个原节点的复制。
通过这个旧新、旧新成对连接的新链表就可以通过：

cur.next.random = cur.random.next;

当前cur.next是新节点，cur是旧节点，用这个语句就可以实现新链表的random关系复制。

接着再将成对的链表拆分开来即可。

public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        Node cur = head;
        while (cur != null) {
            Node tmp = new Node(cur.val);
            tmp.next = cur.next;
            cur.next = tmp;
            cur = tmp.next;
        }
        cur = head;
        while (cur != null) {
            if (cur.random != null) {
                cur.next.random = cur.random.next;
            }
            cur = cur.next.next;
        }

        cur = head.next;
        Node pre = head;
        Node res = head.next;

        while (cur.next != null) {
            pre.next = pre.next.next;
            cur.next = cur.next.next;
            pre = pre.next;
            cur = cur.next;
        }

        pre.next = null;
        return res;
    }

注：最后对pre的操作是因为原题不允许更改原链表的数据。