[剑指offer]复杂链表的复制

我不是女神ヾ 2021-12-19 15:27 201阅读 0赞

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

![412362_1489225139482_4A47A0DB6E60853DEDFCFDF08A5CA249][]

/*
    struct RandomListNode {
        int label;
        struct RandomListNode *next, *random;
        RandomListNode(int x) :
                label(x), next(NULL), random(NULL) {
        }
    };
    */
    class Solution {
    public:
        RandomListNode* Clone(RandomListNode* pHead)
        {
            if(pHead == NULL)return NULL;
            Replica(pHead);
            RandomLink(pHead);
            return Div(pHead);
        }
    
        //[1]复制结点，插入到原结点后方
        void Replica(RandomListNode* pHead)
        {
            RandomListNode* p = pHead;
            while(p!=NULL){
                RandomListNode* pNode=new RandomListNode(p->label);
                pNode->next=p->next;
                p->next=pNode;
                p=pNode->next;
            }
        }
        //[2]还原新结点的random指针
        void RandomLink(RandomListNode* pHead){
            RandomListNode* p = pHead;
            while(p!=NULL){
                if(p->random!=NULL)p->next->random=p->random->next;
                p=p->next->next;
            }
        }
        //[3]拆分
        RandomListNode* Div(RandomListNode* pHead){
            RandomListNode* pRet = pHead->next;
            RandomListNode* p1 = pHead;
            RandomListNode* p2 = pHead->next;
            while(p1!=NULL){
                p1->next = p2->next;
                p1=p2->next;
                if(p1!=NULL){
                    p2->next = p1->next;
                    p2=p1->next;
                }
            }
            return pRet;
        }
    
    };

[412362_1489225139482_4A47A0DB6E60853DEDFCFDF08A5CA249]: /images/20211219/b4d7cadb944a43ebb31ae2f819ca9b9a.png