138. Copy List with Random Pointerv.md

138. 复制带随机指针的链表

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

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

 

示例：

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

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

 

提示：

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

解法一：

//时间复杂度O(n), 空间复杂度O(n)
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node() {}

    Node(int _val, Node* _next, Node* _random) {
        val = _val;
        next = _next;
        random = _random;
    }
};
*/
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(!head) return nullptr;
        if(um.count(head)) return um[head];
        Node* p = new Node(head->val, nullptr, nullptr);
        um[head] = p;
        p->next = copyRandomList(head->next);
        p->random = copyRandomList(head->random);
        return p;
    }
private:
    unordered_map<Node*, Node*> um;
};;

解法一：

思路同第133题的解法二。也可以不使用递归，参考133解法一。

2019/12/09 11:11