题解 | #复杂链表的复制#

/*
struct RandomListNode {
    int label;
    struct RandomListNode *next, *random;
    RandomListNode(int x) :
            label(x), next(NULL), random(NULL) {
    }
};
*/
class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead) {
        CloneNodes(pHead);
        ConnectSiblingNodes(pHead);
        return ReconnectNodes(pHead);
    }
    void CloneNodes(RandomListNode* pHead){
        RandomListNode* cur = pHead;
        while(cur != nullptr){
            RandomListNode* next = cur->next;
            RandomListNode* clone = new RandomListNode(cur->label);
            cur->next = clone;
            clone->next = next;
            cur = next;
        }
    }
    void ConnectSiblingNodes(RandomListNode* pHead){
        RandomListNode* cur = pHead;
        while(cur != nullptr){
            RandomListNode* next = cur->next->next;
            if(cur->random != nullptr){
                cur->next->random = cur->random->next;
            }
            cur = next;
        }
    }
    RandomListNode* ReconnectNodes(RandomListNode* pHead){
        if (pHead == nullptr) return nullptr;
        RandomListNode* r = pHead->next;
        RandomListNode* cur = pHead;
        while(cur != nullptr){
            RandomListNode* next = cur->next->next;
            if(next == nullptr){
                cur->next->next = nullptr;
            }else{
                cur->next->next = next->next;
            }
            cur->next = next;
            cur = next;
        }
        return r;
    }
};