题解 | 复杂链表的复制

/*
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* newHead = new RandomListNode(0);
        RandomListNode *p1=pHead, *p2=newHead;
        while(p1){
            RandomListNode* temp = new RandomListNode(p1->label);
            p2->next = temp;
            temp->next = nullptr;//每一个都当作末尾处理
            p2 = temp;
            p1 = p1->next;
        }
        p1 = pHead, p2=newHead->next;
        while(p1){
            if(p1->random){
                RandomListNode* p11 = pHead;
                RandomListNode* p22 = newHead->next;
                while(p11!=p1->random){
                    p11 = p11->next;
                    p22 = p22->next;
                }
                p2->random = p22;
            }
            p1 = p1->next;
            p2 = p2->next;
        }
        p2 = newHead->next;
        delete newHead;
        return p2;
    }
};

随机指针也是附着在存在的节点上的，所以我的思路是先建立全部节点，然后再找每个节点的随机指针依附的位置。

建立新节点的过程就是手动分配空间，然后把每个pHead链表中的节点值复制到每个对应的新节点中。

因为next指针的对应情况在两个链表中是一致的，所以我们用双指针分别指向两个链表的开头，查找和旧链表的random指针对应的next的位置（p11从头开始遍历next直到与p1->random相等），p22和p11同步操作，就可以找到新链表中p2->random指针指向的位置，然后连接起来。

这样的时间复杂度是O(n^2)，因为每个有random的新节点找random都要从头遍历一次。

空间复杂度为O(n)。