题目描述

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

https://leetcode.cn/problems/fu-za-lian-biao-de-fu-zhi-lcof/

题解

递归 + 哈希

对于递归，我们不需要知道整个问题要怎么解决，我们只需要关注当前节点的复制问题，还有递归的结束条件。

特别的，这道题我们使用记忆化递归的操作来避免重复复制节点，避免陷入递归循环。

但是实际上，执行顺序是先按照 ->next 顺序复制了所有节点（递），然后再回溯根据 copyRandomList(head->next) 的返回结果建立了 ->next 的关系（归）；

另外 ->random 关系也在回溯时建立，所有的 copyRandomList(head->random) 调用都会直接返回 cache[head]，因为所有节点都已经复制并存入了 cache 。

所以其实 copy->random = cache[head->random]; 也是完全没有问题的。

class Solution {
    unordered_map<Node*, Node*> cache;      // 原链表节点对应到新链表节点
public:
    Node* copyRandomList(Node* head) {
        if (!head) return nullptr;
        if (!cache.count(head)) {
            Node* copy = new Node(head->val);
            cache[head] = copy;             // 创建后要马上加入再递归，否则容易陷入链表的循环
            copy->next = copyRandomList(head->next);
            copy->random = copyRandomList(head->random);
        }
        return cache[head];
    }
};

时间复杂度 O(N)，空间复杂度 O(N)

迭代 + 哈希

先复制一个只有 next 指针的普通链表，并建立原链表和复制链表之间节点与节点的对应关系；

random 指针就是链表中的一个节点指向另一个节点，有了对应关系，再遍历原链表，实现 random 指针。

例：A -> B，根据对应关系，我们可以得到 A’ 和 B’，令 A’ -> B’ 即可

class Solution {
public:
    Node* copyRandomList(Node* head) {
        unordered_map<Node*, Node*> oldToNew;   // 原链表和新链表节点的对应关系
        Node* dummyHead = new Node(-1);         // 虚头节点
        Node* p = dummyHead;
        Node* cur = head;
        while (cur) {                           // 先复制普通链表，并建立对应关系
            p->next = new Node(cur->val);
            p = p->next;
            oldToNew[cur] = p;
            cur = cur->next;
        }
        cur = head;
        while (cur) {
            oldToNew[cur]->random = cur->random ? oldToNew[cur->random] : nullptr;
            cur = cur->next;
        }
        return dummyHead->next;
    }
};

时间复杂度 O(N)，空间复杂度 O(N)

迭代空间优化

对迭代方法进行空间优化，哈希的目的在于保存一种对应关系，我们可以利用原链表直接实现对应关系，不用哈希。

思路是在原链表节点的后面插入复制节点，将所有节点复制完成；

然后根据复制节点在原链表节点后面的关系，来代替哈希，并建立 random 指针的关系；

最后再实现 next 指针的指向，将复制的节点连成链表。

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (!head) return nullptr;
        // 1. 在每个节点后面加上一个该节点的复制：A->B to A->A'->B->B'
        for (Node* node = head; node != nullptr; node = node->next->next) {
            Node* copyNode = new Node(node->val);
            copyNode->next = node->next;
            node->next = copyNode;
        }
        // 2. 让每一个被复制出来的节点的 random 指针，指向原节点 random 指针指向节点的后一个节点
        for (Node* node = head; node != nullptr; node = node->next->next) {
            node->next->random =  node->random ? node->random->next : nullptr;
        }
        // 3. 将所有被复制出来的节点连成新的链表，并恢复原链表
        Node* newHead = head->next;
        for (Node* node = head; node != nullptr; node = node->next) {
            Node* oldNext = node->next->next;
            node->next->next = oldNext ? oldNext->next : nullptr;
            node->next = oldNext;
        }
        return newHead;
    }
};