给你一个长度为 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。
需求
- 复制链表
- random指向不同
实现
- 哈希
- 分段
代码
- 哈希
class Solution {
/**
* 深拷贝带随机指针的链表
*
* @param head 原链表的头节点
* @return 复制链表的头节点
*/
public Node copyRandomList(Node head) {
// 特殊情况判断
if (head == null) return null;
// 这个写法第一次见哦！为啥？因为这是看ai的题解，第一次看到这种做法
java.util.Map<Node, Node> map = new java.util.HashMap<>();
// 第一遍遍历：创建所有新节点并建立映射
Node curr = head;
while (curr != null) {
// 当前节点为key，新节点为value
map.put(curr, new Node(curr.val));
curr = curr.next;
}
// 第二遍遍历：根据映射设置新节点的 next 和 random 指针
curr = head;
while (curr != null) {
// 找到curr的克隆节点，将他的next指向下一个节点
map.get(curr).next = map.get(curr.next);
map.get(curr).random = map.get(curr.random);
curr = curr.next;
}
return map.get(head);
}
}
- 分断
class Solution {
/**
* 深拷贝带随机指针的链表（O(1) 空间）
*
* @param head 原链表的头节点
* @return 复制链表的头节点
*/
public Node copyRandomList(Node head) {
if (head == null) {
return null;
}
// 第一步：将每个新节点插入到对应原节点之后，形成交错链表 A -> A' -> B -> B' -> ...
Node curr = head;
while (curr != null) {
Node copy = new Node(curr.val);
// 克隆节点先接上原节点的下一个节点
copy.next = curr.next;
// 原节点指向克隆节点完成交叉插入
curr.next = copy;
// 跳到下一个节点,三者合并实现在curr后面插入克隆节点并且移动到下一个节点
curr = copy.next;
}
// 第二步：利用交错结构设置 random 指针，A'.random = A.random.next
curr = head;
while (curr != null) {
// 判断是否为空
if (curr.random != null) {
// 设置随机指针
curr.next.random = curr.random.next;
}
curr = curr.next.next;
}
// 第三步：拆分交错链表，恢复原链表并提取复制链表
Node dummy = new Node(0);
Node copyCurr = dummy;
curr = head;
while (curr != null) {
// 克隆节点接入复制链表
copyCurr.next = curr.next;
// 复制链表指针后移
copyCurr = copyCurr.next;
// 恢复原链表的next指向
curr.next = copyCurr.next;
// 指针后移
curr = curr.next;
}
return dummy.next;
}
}