题解 | 复杂链表的复制

/*
struct RandomListNode {
    int label;
    struct RandomListNode *next, *random;
    RandomListNode(int x) :
            label(x), next(NULL), random(NULL) {
    }
};
*/
#include <unordered_map>
class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead) {
        if(!pHead) return nullptr;
        unordered_map<RandomListNode*, RandomListNode*> mp;
        RandomListNode* cur = pHead;
        while(cur){
            RandomListNode* ncur = new RandomListNode(cur->label);
            mp[cur] = ncur;
            cur = cur->next;
        }
        cur = pHead;
        RandomListNode* pre = nullptr;
        while(cur){
            if(!pre){
                pre = mp[cur];
            }
            else{
                pre->next = mp[cur];
                pre = mp[cur];
            }
            if(mp[cur]){
                mp[cur]->random = mp[cur->random];
            }
            cur = cur->next;
        }
        return mp[pHead];
    }
};

方法一：hash（key, value找对应）

/*
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 *p = pHead;
        while (p)
        {
            RandomListNode *np = new RandomListNode(p->label);
            np->next = p->next;
            p->next = np;
            p = np->next;
        }
        p = pHead;
        while (p)
        {
            RandomListNode *np = p->next;
            if (!p->random)
                np->random = nullptr;
            else
                np->random = p->random->next;
            p = np->next; // 不用检查末尾节点因为np必然不为空，每一个p后面都复制了一个np
        }
        RandomListNode *ans = pHead->next;
        p = pHead;
        RandomListNode *cur = nullptr;
        while (p)
        {
            if (cur)
            {
                cur->next = p->next;
                cur = cur->next;
            }
            else
            {
                cur = p->next;
            }
            p->next = p->next->next;
            p = p->next;
            cur->next = nullptr; // 断开连接避免影响，其实一般没啥影响毕竟末尾不断开的话最后剩下的也是空指针。而原链表跨过新链表也指向最后的空指针。
        }
        return ans;
    }
};

方法二：

链表老节点和新节点穿插找对应（刚好就在下一个）

两个方法的区别就在于找对应的方法。为什么要找对应是因为random不一定能生成所有的新节点，所以考虑用next生成，但是这样就找不到random（指针是这样，不方便随机查找），所以我们要想找到的方式。

最简单就是不能随机查找就让它能随机查找，那么我就添加一个哈希表进去。这是第一个方案。空间O(n) 时间O(n);

难想到一点是直接从老的位置遍历时找新的位置，这就是穿插，看过一个案例就能想到了。空间O(1) 时间O(n);

为了不用重新处理首节点，搞一个头节点出来会让代码更清晰，也是常用做法。(我没有这样写是我的问题（）

官方的一个方法是这样写的，可以看看官方解释。