共计 2985 个字符,预计需要花费 8 分钟才能阅读完成。
LeetCode 138:复制带随机指针的链表
https://leetcode-cn.com/probl…
一、题目形容
给你一个长度为 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 作为传入参数。
节点定义 :
class Node {
int val;
Node next;
Node random;
public Node(int val) {
this.val = val;
this.next = null;
this.random = null;
}
}
二、示例
输出:head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输入:[[7,null],[13,0],[11,4],[10,2],[1,0]]
三、思路
额定空间复杂度为 O(1) 的写法
1、在原链表每个节点前面,复制一个新的节点,并连到老节点前面
即:
复制前:1 -> 2 -> 3,
复制后:1 -> 1\` -> 2 -> 2\` -> 3 -> 3\`
2、将原节点 random 指针的关系,在新节点中复制一份
3、拆散新老节点
额定空间复杂度为 O(N) 的写法
1、应用 Map 存储新老节点,Key:老节点,Value:新节点
2、结构老节点对应的新节点
3、调整新节点的 next 指针、调整新节点的 random 指针
四、源码
额定空间复杂度为 O(1) 的写法
/**
* @author Java 和算法学习:周一
*/
public Node copyRandomList(Node head) {if (head == null) {return null;}
// 1. 将新节点插入到老节点前面
// 调整前:1 -> 2 -> 3 -> null,调整后:1 -> 1` -> 2 -> 2` -> 3 -> 3` -> null
Node current = head;
Node next = null;
while (current != null) {
// 标记原链表中以后节点的 next 节点
next = current.next;
// 在原链表以后节点的前面插入新节点
current.next = new Node(current.val);
// 调整新插入节点的 next 节点
current.next.next = next;
// 以后节点后移
current = next;
}
// 2. 调整新插入节点的 random 指针
Node copy = null;
current = head;
while (current != null) {
// 新节点
copy = current.next;
// 标记原链表中以后节点的 next 节点
next = current.next.next;
// 调整新节点的 random 节点
copy.random = current.random != null ? current.random.next : null;
// 以后节点后移
current = next;
}
// 3. 拆散新老节点
current = head;
// 记录新链表的头节点
Node res = head.next;
while (current != null) {
// 新节点
copy = current.next;
// 标记原链表中以后节点的 next 节点
next = current.next.next;
// 以后节点的 next 节点指向原链表中以后节点的 next 节点(行将老节点的援用调整回去)current.next = next;
// 新节点的 next 节点指向 原链表中以后节点 next 节点 的 next 节点(即抽出新节点的援用)copy.next = next != null ? next.next : null;
// 以后节点后移
current = next;
}
// 返回新链表的头节点
return res;
}
额定空间复杂度为 O(N) 的写法
/**
* @author Java 和算法学习:周一
*/
public Node copyRandomListByMap(Node head) {
// Key:老节点,Value:新节点
HashMap<Node, Node> map = new HashMap<>();
Node current = head;
while (current != null) {
// 结构老节点对应的新节点
map.put(current, new Node(current.val));
current = current.next;
}
current = head;
while (current != null) {
// 调整新节点的 next 指针
map.get(current).next = map.get(current.next);
// 调整新节点的 random 指针
map.get(current).random = map.get(current.random);
current = current.next;
}
return map.get(head);
}
五、测试后果
额定空间复杂度为 O(1) 的写法
额定空间复杂度为 O(N) 的写法
从 LeetCode 官网的测试后果能够看出,执行用时没有差距,内存耗费(即额定空间复杂度)的差距就很显著了,一个战胜 99.94% 的用户,一个只战胜了 48.64% 的用户。