参考博客：https://blog.csdn.net/willduan1/article/details/53352759

第三种解法很巧妙

 

主要思路分为三步：

1.复制每个节点的label和next，紧插在该节点后面

2.复制random指针

3.拆分链表

    public RandomListNode Clone(RandomListNode pHead) {
        if (pHead == null)
            return null;

        //复制并插入
        RandomListNode p = pHead;
        while (p != null) {
            RandomListNode tmp = new RandomListNode(p.label);
            tmp.next = p.next;
            p.next = tmp;
            p = tmp.next;
        }

        //复制random指针
        p = pHead;
        while (p != null) {
            if (p.random != null)
                p.next.random = p.random.next;
            p = p.next.next;
        }

        //拆分链表
        RandomListNode head = pHead.next;
        RandomListNode q = head;
        p = pHead;
        while (q.next != null){
            p.next = q.next;
            p = p.next;

            q.next = p.next;
            q = q.next;
        }
        p.next = null;
        return head;

    }