题解 | 复杂链表的复制

/*
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 == nullptr)
            return nullptr;

        RandomListNode* curr = pHead;
        RandomListNode* orgNext = nullptr;
        while (curr != nullptr) {
            orgNext = curr->next;
            curr->next = new RandomListNode(curr->label);
            
            //update the newly added node
            curr->next->next = orgNext;

            curr = orgNext;
        }
    
    
        // update the random node
        curr = pHead;
        
        while (curr != nullptr) {
            if (curr->random == nullptr) {
                // the random pointer pointing to nullptr
                curr->next->random = nullptr;
                curr = curr->next->next;
            } else {
                curr->next->random = curr->random->next;
                curr = curr->next->next;
            }
        }

        // split the list
        curr = pHead;
        orgNext = nullptr;
        RandomListNode* dupHead = pHead->next;
        while (curr != nullptr) {
            orgNext = curr->next;
            if (orgNext == nullptr)
             break;
            curr->next = curr->next->next;
            curr = orgNext;
        }


        return dupHead;














































        // RandomListNode* curr = pHead;
        // RandomListNode* tmp = nullptr;
        // // duplicate the node in place
        // while (curr != nullptr) {
        //     tmp = curr;
        //     RandomListNode* dupNode = new RandomListNode(tmp->label);
        //     curr->next = dupNode;
        //     dupNode->next = tmp->next;;
        //     curr = dupNode->next;
        // }

        // // add random link 
        // curr = pHead;
        // RandomListNode* cpyHead = pHead->next;
        // // RandomListNode* tmpRand  = cpyHead;
        // // while (tmpRand->next != nullptr) {
        // //     tmpRand->random = curr->random->next;
        // //     tmpRand = tmpRand->next->next;
        // //     curr = curr->next->next;
        // // }

        // tmp = cpyHead;
        // while (tmp->next != nullptr) {
        //     tmp->random = curr->random->next;
        //     tmp = tmp->next->next;
        //     curr = curr->next->next;
        // }



        // // separate the structure
        // // tmp = pHead;
        // // RandomListNode* tmpCpy = cpyHead;


        // RandomListNode* prev = nullptr;
        // // curr = cpyHead;
        // curr = pHead->next;

        // while (curr->next != nullptr) {
        //     prev = curr->next;
        //     curr->next = curr->next->next;
        //     curr = prev->next;
        // }

        // // RandomListNode* orgNext = nullptr;
        // // RandomListNode* cpyNext = nullptr;
        // // RandomListNode* interimOrgNext = nullptr;
        // // RandomListNode* interimCpyNext = nullptr;
        // // while (tmpCpy->next != nullptr) {
        // //     orgNext = tmpCpy->next;
        // //     cpyNext = orgNext->next;

        // //     interimOrgNext = tmp->next->next;
        // //     interimCpyNext = tmpCpy->next->next;

        // //     tmp->next = orgNext;
        // //     tmpCpy->next = cpyNext;

        // //     tmp = interimOrgNext;
        // //     tmpCpy = interimCpyNext;
        // // }

        // return cpyHead;




      
    }
};

不能直接的去创建单独的一个新的复制好的链表，因为这里还有Random指针，在直接创建好之后再想去找到原来Random所指向的对象就很困难了（区别于找到相同的label值，这里我们并不关注label的值，更关注的其实是链表的结构

我们通过in place的方式去duplicate链表，扩展原来的链表元素，这一步的目的是服务于刚刚random指针无法定位的情况。现在就可以通过next的指针去寻找对应的random指向的对象，根据原来的链表情况。

补充好random指针后最后一步是拆分链表，这一步的时候同样需要双指针，比较容易