本文共 1525 字，大约阅读时间需要 5 分钟。

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

要求返回这个链表的****。

示例：

输入： {“KaTeX parse error: Expected '}', got 'EOF' at end of input: …":"1","next":{"id”:“2”,“next”:null,“random”:{“KaTeX parse error: Expected 'EOF', got '}' at position 9: ref":"2"}̲,"val":2},"rand…ref”:“2”},“val”:1}

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

提示：

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

C++1

使用两次遍历+hash表。

/*// 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) {
           unordered_map
   
     nodemap;        Node *temp = head;        Node *new_head = new Node(0,NULL,NULL);        Node *copy_temp = new_head;                while(temp){
               copy_temp->next = new Node(temp->val,NULL,NULL);            nodemap[temp] = copy_temp->next;                        temp = temp->next;            copy_temp = copy_temp->next;        }                Node * random_temp = NULL;        temp = head;        copy_temp = new_head->next;                while(temp){
               random_temp = temp->random;            if(random_temp){
                   copy_temp->random = nodemap[random_temp];            }else{
                   copy_temp->random = NULL;            }            temp = temp->next;            copy_temp = copy_temp->next;        }                return new_head->next;    }};
   

转载地址：http://rlomf.baihongyu.com/