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

构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。
你的代码 只 接受原链表的头节点 head 作为传入参数。

提示：

• 0 <= n <= 1000
• $-10^4$ <= Node.val <= $10^4$
  Node.random 为 null 或指向链表中的节点。
  注意：本题与主站 138 题相同：138

题解1 哈希表

/*
// Definition for a Node.
class Node {
public:int val;Node* next;Node* random;Node(int _val) {val = _val;next = NULL;random = NULL;}
};
*/class Solution {
public:Node* copyRandomList(Node* head) {if(! head) return nullptr;Node *p, *q, *f, *cphead;f = p = q = new Node(head->val);cphead = head;/** 受判题启发：给结点编号（array-like）1. 变量需要3个map，分别记录结点-编号，编号-地址/结点，结点编号-其随机结点编号2. 关键问题是：随机结点是在整个链表的基础上去看，即next建立了一条完整的链表，之后才有random的关系，即random结点是已经存在的结点，不能再new了**/unordered_map<Node*, int> idxmap;unordered_map<int, Node*> addrmap;unordered_map<int, int> randomidxmap;/** 对空特殊处理（可以让idx从1开始，避开0）int idx = 0;idxmap[nullptr] = 1001;randomidxmap[idxmap[nullptr]] = idxmap[nullptr];addrmap[randomidxmap[idxmap[nullptr]]] = nullptr;**/int idx = 1;// 结点编号，建立新链表while(head){idxmap[head] = idx;idxmap[q] = idx;addrmap[idx] = q;head = head->next;if(head)q->next = new Node(head->val);else q->next = nullptr;q = q->next;idx ++;}// 记录原链表的random关系while(cphead){randomidxmap[idxmap[cphead]] = idxmap[cphead->random];cphead = cphead->next;}// 复刻while(p){p->random = addrmap[randomidxmap[idxmap[p]]];p = p->next;}return f;}
};

题解2 回溯+哈希

class Solution {
public:// key = 原结点// value = 新结点unordered_map<Node*, Node*> Nodemap;Node* copyRandomList(Node* head) {if(! head) return nullptr;// 需要克服的问题是：不知道random指向的结点是否建立过	// 如果没建立过，则新建if(! Nodemap.count(head)){Node* newnode = new Node(head->val);Nodemap[head] = newnode;newnode->next = copyRandomList(head->next);newnode->random = copyRandomList(head->random); }// 建立过直接返回return Nodemap[head];}
};

哈希思路精简

class Solution {
public:Node* copyRandomList(Node* head) {if(! head) return nullptr;map<Node*, Node*> kkmap;Node* autohead = head;// 新建链表// kkmap保证每个结点对应的都是新地址while(autohead){kkmap[autohead] = new Node(autohead->val);autohead = autohead->next;}autohead = head;// 建立next和random关系while(autohead){kkmap[autohead]->next = kkmap[autohead->next];kkmap[autohead]->random = kkmap[autohead->random];autohead = autohead->next;}return kkmap[head];}
};

题解3 优化迭代

class Solution {
public:Node* copyRandomList(Node* head) {if(! head) return nullptr;Node* ll = head;Node* newhead;// copy to the original linkwhile(ll){Node* nextll = ll->next;Node* tmp = new Node(ll->val);ll->next = tmp;tmp->next = nextll;ll = nextll;}// Handle random point First !!!!(next info exists)ll = head;while(ll){Node* cphead = ll->next;cphead->random = ll->random ? ll->random->next : nullptr;ll = cphead->next;}newhead = head->next;ll = head;// Handle next point and restore the original onewhile(ll){Node* cphead = ll->next;// 断开连接ll->next = cphead->next;cphead->next = cphead->next ? cphead->next->next : nullptr;ll = ll->next;}return newhead;}
};