复杂链表的复制

复杂链表的复制

题目描述

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

解题思路

• 根据原始链表中的每个节点，创建一个克隆节点，并且链接在它的后面，先不考虑随机指针
• 复制随机指针，如果原始链表中P的随机指针指向S，那么它的克隆指针P’应该指向S’，而这一步骤可以通过P'->random=P->random->next快速的定位到
• 把链表拆分，奇数位置的节点为原链表的节点，偶数位置的为新复制的链表节点

贴一张图，很精髓

class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead)
    {
        CloneNode(pHead);//在旧链表中的每个节点后面创建克隆节点，构造新链表
        ConnectNode(pHead);//复制随机指针
        return ReConnectNode(pHead);//将链表拆分
    }
    //在旧链表中的每个节点后面创建克隆节点，构造新链表
    void CloneNode(RandomListNode *pHead){
        RandomListNode *p=pHead;
        while(p!=NULL){
            RandomListNode *clone=new RandomListNode(0);
            clone->label=p->label;
            clone->random=NULL;
            clone->next=p->next;
            p->next=clone;
            p=clone->next;
        }
    }
    //复制随机指针
    void ConnectNode(RandomListNode *pHead){
        RandomListNode *p=pHead;
        while(p!=NULL){
            RandomListNode *clone=p->next;
            if(p->random!=NULL)
                //p->random->next指向的是clone的节点
                clone->random=p->random->next;
            p=clone->next;
        }
    }
    //将链表拆分，返回新创建的链表头节点
    RandomListNode *ReConnectNode(RandomListNode *pHead){
        RandomListNode *p=pHead;
        //p1用来遍历，p2保存复制链表头节点
        RandomListNode *p1=NULL,*p2=NULL;
        if(p!=NULL){
            p1=p2=p->next;
            p->next=p1->next;
            p=p->next;
        }
        while(p!=NULL){
            p1->next=p->next;
            p1=p1->next;
            p->next=p1->next;
            p=p->next;
        }
        return p2;
    }
};