题解 | 复杂链表的复制

/*
struct RandomListNode {
    int label;
    struct RandomListNode *next, *random;
    RandomListNode(int x) :
            label(x), next(NULL), random(NULL) {
    }
};
*/
class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead) {
        //1.hash表处理，官方题解存储每个节点的地址映射关系,并进行两次遍历；
        //此处进行一次遍历，但每次遍历进行两组map查找；
        if(pHead == nullptr){
            return nullptr;
        }
        //若原链表中节点有重复的label值，那么map的键应换为原链表节点的地址
        unordered_map<int, RandomListNode*> MyMap;
        RandomListNode *head = new RandomListNode(pHead->label), *front = head;

        for(RandomListNode *pfront=pHead; pfront!=nullptr;){
            if(pfront->random==nullptr){
                front->random = pfront->random;
            }
            else{
                if(MyMap[pfront->random->label]==nullptr){
                    RandomListNode *temp = new RandomListNode(front->label);
                    front->random = temp;
                    MyMap[pfront->random->label] = temp;
                }
                else{
                    front->random = MyMap[pfront->random->label];
                }
            }

            if(pfront->next==nullptr){
                break;
            }
            else{
                if(MyMap[pfront->next->label]==nullptr){
                    RandomListNode *temp1 = new RandomListNode(pfront->next->label);
                    front->next = temp1;
                    MyMap[pfront->next->label] = temp1;
                }
                else{
                    front->next = MyMap[pfront->next->label];
                }
            }

            pfront = pfront->next;
            front = front->next;
            front->label = pfront->label;
        }
        return head;

        //2.双指针
        //牛客394721436号的方法：将原链表的每个节点与新链表中的每个节点进行对应
        //省略通过查找的方式来获取random指向的节点以及避免重复开辟内容相同的空间
        // if (!pHead) return NULL;
        // RandomListNode *head = pHead;
        // while (head)
        // {
        //     RandomListNode *clone= new RandomListNode(head->label);
        //     //clone->label = head->label;
        //     clone->next = head->next;
        //     head->next = clone;
        //     head = clone->next;
        // }
 
        // RandomListNode *head1 = pHead;
        // RandomListNode *clone1;
        // while (head1)
        // {
        //     clone1 = head1->next;
        //     if (head1->random != nullptr) clone1->random = head1->random->next;
        //     head1 = clone1->next;
        // }
 
        // RandomListNode *head2 = pHead;
        // RandomListNode *clone2;
        // RandomListNode *cloned = pHead->next;
        // while (head2)
        // {
        //     clone2 = head2->next;
        //     head2->next = clone2->next;
        //     head2 = head2->next;
        //     if(head2) clone2->next = head2->next;
        // }
        // return cloned;
    }
};