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

在不限制时间复杂度的情况下，这题难度并不高。 首先遍历一次链表来深拷贝出一个新链表，这次深拷贝不考虑random的值，仅将链表的label和next深拷贝出来。这样就得到了链表的基本骨架。再用一个二重循环遍历链表，每次处理一个结点，通过一个循环来从骨架链表中找到一个label域和原链表中ramdom域的label域相等的结点，将该结点赋给被处理结点的random域。 这样做使用了一个二重循环，时间复杂度为O(n^2)，空间复杂度为O(1)。

/*
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;
        }
        RandomListNode* newHead = new RandomListNode(pHead->label);
        RandomListNode* p = pHead->next;
        RandomListNode* pre = newHead;
        while(p){
            pre->next = new RandomListNode(p->label);
            pre = pre->next;
            p = p->next;
        }
        p = pHead;
        pre = newHead;
        while(pre){
            if(p->random == nullptr){
                p = p->next;
                pre = pre->next;
                continue;
            }
            RandomListNode* temp = newHead;
            while(temp){
                if(temp->label == p->random->label){
                    pre->random = temp;
                }
                temp = temp->next;
            }
            pre = pre->next;
            p = p->next;
        }
        
        return newHead;
    }
};

若对上面这种做法的时间复杂度不满意，可以使用空间换时间的方法，在第一次遍历构建骨架时就将对应的random域信息存在一个数组中，将新建结点的信息存在另一数组中，这样在第二次遍历时只用一重循环即可找到对应的random域。这样做时间复杂度为O(n)，空间复杂度为O(n)。 这里又个小坑，最开始为了追求代码简洁，在while循环中使用了形如array[i++]这种形式的写法，但是会导致结果与预想的不符。最后还是老老实实的用array[i];i++;这种形式，这样结果就正常了。偷懒需谨慎。

/*
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;
        }
        RandomListNode* newHead = new RandomListNode(pHead->label);
        RandomListNode* p = pHead->next;
        RandomListNode* pre = newHead;
        RandomListNode* arr[100];
        int index = 0;
        arr[index] = newHead;
        int randomList[100] = {-1};
        if(pHead->random){
            randomList[index++] = pHead->random->label;
        }
        else{
            randomList[index++] = -1;
        }
        while(p){
            pre->next = new RandomListNode(p->label);
            if(p->random){
                randomList[index] = p->random->label;
            }
            else{
                randomList[index] = -1;
            }
            pre = pre->next;
            arr[index++] = pre;
            p = p->next;
        }
        pre = newHead;
        index = 0;
        while(pre){
            if(randomList[index] == -1){
                index++;
                pre->random = nullptr;
                pre = pre->next;
                continue;
            }
            pre->random = arr[randomList[index]-1];
            pre = pre->next;
            index++;
        }
        return newHead;
    }
};