【剑指Offer】（链表）复杂链表的复制

偏执的太偏执、 2022-03-17 14:22 205阅读 0赞

**题目链接**：[https://www.nowcoder.com/practice/f836b2c43afc4b35ad6adc41ec941dba?tpId=13&tqId=11178&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking][https_www.nowcoder.com_practice_f836b2c43afc4b35ad6adc41ec941dba_tpId_13_tqId_11178_tPage_2_rp_2_ru_ta_coding-interviews_qru_ta_coding-interviews_question-ranking]

#### 题目描述 ####

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

#### 解决方法 ####

/* 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) return nullptr;
            //[1]复制并创建新节点，插入到原节点后方
            RandomListNode *pNode=pHead;
            while(pNode){ 
                RandomListNode *pClone=new RandomListNode(0);
                pClone->label=pNode->label;
                pClone->next=pNode->next;
                pNode->next=pClone;
                pNode=pClone->next;
            }
            //[2]设置复制出来的新节点的random指针
            pNode=pHead;
            while(pNode){ 
                RandomListNode *pClone=pNode->next;
                if(pNode->random) pClone->random=pNode->random->next;
                pNode=pClone->next;
            }
            //[3]拆分链表，将链表拆分为原链表和复制后的链表
            pNode=pHead;
            RandomListNode *pCloneHead=pNode->next, *pClone=pNode->next;
            pNode->next=pClone->next;
            pNode=pNode->next;
            while(pNode){ 
                pClone->next=pNode->next;
                pClone=pClone->next;
                pNode->next=pClone->next;
                pNode=pNode->next;
            }
            return pCloneHead;
            
        }
    };

[https_www.nowcoder.com_practice_f836b2c43afc4b35ad6adc41ec941dba_tpId_13_tqId_11178_tPage_2_rp_2_ru_ta_coding-interviews_qru_ta_coding-interviews_question-ranking]: https://www.nowcoder.com/practice/f836b2c43afc4b35ad6adc41ec941dba?tpId=13&tqId=11178&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking