题目：

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

思路：

1.先把每个节点复制出一个节点并把每个复制出的节点连接到原来节点后面
2.把原来每个节点的random指针复制到对应复制出的节点上
3.把每个复制出来的节点分离出来

public class Clone {
    private RandomListNode pHead;
    //输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），
    // 返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

    //思路 ： 1.先把每个节点复制出一个节点并把每个复制出的节点连接到原来节点后面
    //       2.把原来每个节点的random指针复制到对应复制出的节点上
    //       3.把每个复制出来的节点分离出来

    class RandomListNode {
        int label;
        RandomListNode next = null;
        RandomListNode random = null;

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

    }

    public RandomListNode Clone(RandomListNode pHead) {
        //第一步
        RandomListNode cur = pHead;
        while (cur != null) {
            RandomListNode newNode = new RandomListNode(cur.label);
            newNode.next = cur.next;
            cur.next = newNode;
            cur = newNode.next;
        }

        //第二步
        RandomListNode cur2 = pHead;
        while (cur2 != null) {
            if (cur2.random != null) {
                cur2.next.random = cur2.random.next;
            }
            cur2 = cur2.next.next;
        }

        //第三步
        RandomListNode newHead = pHead.next;
        RandomListNode pointer = newHead;
        pHead.next = newHead.next;
        pHead = pHead.next;
        while (pHead != null) {
            pointer.next = pHead.next;
            pointer = pointer.next;
            pHead.next = pointer.next;
            pHead = pointer.next;
        }

        return newHead;
    }
}