问题背景
给你一个长度为
n
n
n 的链表，每个节点包含一个额外增加的随机指针
r
a
n
d
o
m
random
random，该指针可以指向链表中的任何节点或空节。
构造这个链表的 深拷贝。 深拷贝应该正好由
n
n
n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的
n
e
x
t
next
next 指针和
r
a
n
d
o
m
random
random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
例如，如果原链表中有
X
X
X 和
Y
Y
Y 两个节点，其中
X
.
r
a
n
d
o
m
=
Y
X.random = Y
X.random=Y。那么在复制链表中对应的两个节点
x
x
x 和
y
y
y，同样有
x
.
r
a
n
d
o
m
=
y
x.random = y
x.random=y。
返回复制链表的头节点。
数据约束
- 0 ≤ n ≤ 1000 0 \le n \le 1000 0≤n≤1000
- − 1 0 4 ≤ N o d e . v a l ≤ 1 0 4 -10 ^ 4 \le Node.val \le 10 ^ 4 −104≤Node.val≤104
- N o d e . r a n d o m Node.random Node.random 为 n u l l null null 或指向链表中的节点。
解题过程
经典链表操作题，解决的关键在于能否想到把新建的复制节点添加到原节点的后一个。
通过上述方案复制完整个链表之后，只要能够分离链表即可，参考 奇偶链表，本题中由于原链表的后一个节点是它本身的复制，一定存在，分离的时候可以少一个判断。
注意数据范围，头节点可能为空，要单独处理。
具体实现
/*
// Definition for a Node.
class Node {
int val;
Node next;
Node random;
public Node(int val) {
this.val = val;
this.next = null;
this.random = null;
}
}
*/
class Solution {
public Node copyRandomList(Node head) {
// 特判头节点为空的情形
if(head == null) {
return null;
}
// 在原链表的每个节点之后新建复制节点
Node cur = head, next;
while(cur != null) {
next = cur.next;
cur.next = new Node(cur.val, cur.next); // 题中没说明这个构造器，实际上是存在的
cur.next.next = next;
cur = cur.next.next;
}
// 重置工作指针
cur = head;
// 给每个新节点的随机域赋值
while(cur != null) {
if(cur.random != null) {
cur.next.random = cur.random.next;
}
cur = cur.next.next;
}
// 分离原链表和复制之后的链表
Node copyHead = head.next, copy;
cur = head;
while(cur.next.next != null) {
copy = cur.next; // 记录下一个节点
cur.next = cur.next.next; // 调整原链表的 next 指针
copy.next = copy.next.next; // 调整新链表的 next 指针
cur = cur.next; // 后移工作指针
}
// 原链表的最后一个节点要指空
cur.next = null;
return copyHead;
}
}