35-复杂链表的复制

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。

复杂链表结构如下：

public class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null; //这里有一个random节点

    RandomListNode(int label) {
        this.label = label;
    }
}

复杂链表

绿色箭头表示random的连接。

容易想到的方法是首先不考虑random连接，仅复制next连接，这样复制出来新的链表。然后在根据给的链表中random指向的结点距离当前结点的距离依样在新的链表上加上random连接。这种方法时间复杂度较高。

假如使用一个hashmap记录对应关系，时间复杂度会降低，但会增加空间复杂度。

这个问题的关键在于random是随机的，怎么样能够确定random的指向呢？

有没有更好的方法呢？

其实关键就是random链接的复制，如何处理random所链接的两个节点的对应关系呢？我们可以这样操作，

在原链表上的每一个节点后面都增加一个复制的结点，然后在将random链接添加上，然后在分离两个链表。

 public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        Node p = head;
        while (p != null) { //复制节点，比如原来是ABC,复制节点后为AABBCC
            Node duplicate = new Node(p.val);
            duplicate.next = p.next;
            p.next = duplicate;
            p = p.next.next;
        }
        p = head;
        while (p != null) { //复制random
            p.next.random = p.random.next;//p节点的复制节点的random指向p的random节点的下一个节点
            p = p.next.next;
        }
        p = head;
        Node result = p.next;
        Node cur = result;
        while (p != null && cur != null) { //将AABBCC分拆为ABC ABC
            p.next = p.next.next;
            p = p.next;
            cur.next = cur.next.next;
            cur = cur.next;
        }
        return result;
    }