LeetCode-剑指35-复杂链表的复制

1、哈希表+递归

题目的难点在于每个链表节点同时存在next和random指针，其中特别是random指针指向随机的对象，我们很难在一次循环中将random指针指向正确的对象。为了解决以上的问题，我们可以使用哈希表+递归的方法来进行解决。

我们可以利用哈希表来记录原节点与新节点之间的关系，如果一个节点已经被复制完成则可以直接调用哈希表进行使用。此外为了解决random指针指向随机对象的问题，我们可以使用递归的方法进行解决。在每次递归过程中，若random指向的对象已经被创建，则可以直接使用哈希表进行查询，否则我们就继续递归的调用函数创建指向对象的复制节点。

class Solution {
public:
    unordered_map<Node*, Node*> cachedNode;

    Node* copyRandomList(Node* head) {
        if (head == nullptr) {
            return nullptr;
        }
        if (!cachedNode.count(head)) {
            Node* headNew = new Node(head->val);
            cachedNode[head] = headNew;
            headNew->next = copyRandomList(head->next);
            headNew->random = copyRandomList(head->random);
        }
        return cachedNode[head];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

2、节点拆分+迭代

我们可以遍历每个节点，在每个节点之后加上该节点的复制节点。而后我们可以遍历每个节点，将其random指针指向的节点的下一个节点赋给复制节点的random指针，值得注意的是，我们在这里需要考虑指针为空的情况。最后我们将拆分的节点与原先的节点进行分离，最终得到复制后的链表。

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (head == nullptr) {
            return nullptr;
        }
        for (Node* node = head; node != nullptr; node = node->next->next) {
            Node* nodeNew = new Node(node->val);
            nodeNew->next = node->next;
            node->next = nodeNew;
        }
        for (Node* node = head; node != nullptr; node = node->next->next) {
            Node* nodeNew = node->next;
            nodeNew->random = (node->random != nullptr) ? node->random->next : nullptr;
        }
        Node* headNew = head->next;
        for (Node* node = head; node != nullptr; node = node->next) {
            Node* nodeNew = node->next;
            node->next = node->next->next;
            nodeNew->next = (nodeNew->next != nullptr) ? nodeNew->next->next : nullptr;
        }
        return headNew;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24