[LeetCode][138]【学习日记】深拷贝带有随机指针的链表
题目描述
138.随机链表的复制
给你一个长度为 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 作为传入参数。
注意点
- random 是一个指向节点的指针
- 复制链表中的指针都不应指向原链表中的节点
哈希表做法
- 这道题的难点在于：
- 当按顺序复制原链表时，当前被复制的节点的 random 可能指向一个还未复制到的节点
- 如何确定新链表中这个节点的 random 指针指向与原链表的 random 指针指向的相同位置的节点（如下图，如何保证第二个 3 的 random 指针指向的是第一个节点而不是第三个节点）
- 解决思路：
- 针对难点1，选择先复制构建一条普通的单向链表，然后再处理其中每个节点的 random 指针，这样可以保证 random 指针指向的节点都先创建过
- 针对难点2，可以想到，我们必须构建原链表节点与新链表节点的联系 m[p] = pn，这样才能依据原链表节点中某个节点的 random 指针找到指向的原链表节点，再由此链表节点找到对应的新链表的节点 pn->random = m[p->random]
Node* copyRandomList(Node* head) {Node *p = head, *dum = new Node(0), *pn = dum;map<Node*, Node*> m;//先复制构建一条普通的单向链表while(p){pn->next = new Node(p->val);pn = pn->next;m[p] = pn;//构建原链表节点与新链表节点的联系p = p->next;}p = head; pn = dum->next;//开始处理新链表节点的random指针的指向while(p){//根据两条链表之间的联系找到 random 指向的新链表的节点pn->random = m[p->random];p = p->next;pn = pn->next;}return dum->next;}
PS：针对如何建立两条链表之间节点一一对应的联系，还有另外一种做法：将两条链表按位置合成一条后进行 random 指针的处理，然后再拆分
node1→node1_new→node2→node2_new→⋯