4/8-剑指offer

1.复杂链表的复制
思路：第一步，复制原始链表的任意节点，并将复制节点链接到原节点后面；第二步，如果原始链表上的节点N的指针指向s，那对应复制节点N’指向s的复制节点s’；第三步，将长链表按奇数和偶数位置，分成两个链表。

/*
struct RandomListNode {
    int label;
    struct RandomListNode *next, *random;
    RandomListNode(int x) :
            label(x), next(NULL), random(NULL) {
    }
};
*/
class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead)
    {
         /*
        *解题思路：
        *1、遍历链表，复制每个结点，如复制结点A得到A1，将结点A1插到结点A后面；
        *2、重新遍历链表，复制老结点的随机指针给新结点，如A1.random = A.random.next;
        *3、拆分链表，将链表拆分为原链表和复制后的链表
         */
        //复制
        if(!pHead) return NULL;
        RandomListNode *cur=pHead;
        while(cur!=NULL)
        {
            RandomListNode *p=new RandomListNode(cur->label);
            p->next=cur->next;
            cur->next=p;
            cur=p->next;
        }
        //重新遍历
        cur=pHead; 
        RandomListNode *p;
        while(cur!=NULL)
        {
            p=cur->next;
            if(cur->random!=NULL)
           {
            p->random=cur->random->next;
           }  
           cur=p->next;
        }
        //拆分
        RandomListNode *clone=pHead->next;
        RandomListNode *tmp;
        cur=pHead;
        while(cur->next!=NULL)
        {
            tmp=cur->next;
            cur->next=tmp->next;
            cur=tmp;            
        }
        return clone;   
    }
};