138-copy-list-with-random-pointer.md

138. Copy List with Random Pointer - 复制带随机指针的链表

给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。

要求返回这个链表的深拷贝。 

 

示例：

输入：
{"$id":"1","next":{"$id":"2","next":null,"random":{"$ref":"2"},"val":2},"random":{"$ref":"2"},"val":1}

解释：
节点 1 的值是 1，它的下一个指针和随机指针都指向节点 2 。
节点 2 的值是 2，它的下一个指针指向 null，随机指针指向它自己。

 

提示：

1. 你必须返回给定头的拷贝作为对克隆列表的引用。

---

题目标签：Hash Table / Linked List

题目链接：LeetCode / LeetCode中国

题解

Language	Runtime	Memory
cpp	48 ms	3.6 MB

/**
 * Definition for singly-linked list with a random pointer.
 * struct RandomListNode {
 *     int label;
 *     RandomListNode *next, *random;
 *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
 * };
 */
class Solution {
public:
    unordered_map<RandomListNode*, RandomListNode*> M;
    RandomListNode *copyRandomList(RandomListNode *head) {
        if (!head) return NULL;
        if (M.count(head)) return M[head];
        RandomListNode* tmp = new RandomListNode(head->label);
        M.insert({head, tmp});
        if (head->next) tmp->next = copyRandomList(head->next);
        if (head->random) tmp->random = copyRandomList(head->random);
        return tmp;
    }
};
static auto _ = [](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();