【剑指offer】复杂链表的复制

这道题有两种思路。第一种普通思路：先顺序复制并且设置好next指针，让新节点的random指向老链表中对应的节点，并且开一个map,一边复制一边存下新旧对应节点地址映射。第二遍遍历根据map把新节点中的random指针都调整正确。这个map消耗了额外空间。
第二种思路：省去这个map，要求是仍然从老节点能直接找到对应的新节点，则方法为把新节点全都缀连在老节点之后。等设置好所有的random之后再拆分两个链表。代码如下。
注意最后新老链表都要还原否则不通过。

public class Solution {
    public RandomListNode Clone(RandomListNode pHead)
    {
        if (pHead==null) return null;
        RandomListNode i=pHead, newNode=null;
        while(i!=null)
        {
            newNode = new RandomListNode(i.label);
            newNode.next= i.next;
            i.next = newNode;
            i=i.next.next;
        }
        i=pHead;
        while(i!=null)
        {
            newNode=i.next;
            if (i.random == null) newNode.random=null;
            else
            newNode.random=i.random.next;
            i=newNode.next;
        }
        i=pHead;
        newNode=pHead.next;
        RandomListNode res = pHead.next;
        while(i!=null)
        {
           newNode=i.next;
           i.next=newNode.next;
           if (newNode.next!=null)
               newNode.next=newNode.next.next;
           i=i.next;
        }
        return res;
    }
}