盒子
盒子
文章目录
  1. 题目
  2. 分析
  3. 原地复制再拆分
  4. 使用Map

复杂链表的复制

题目

实现复制一个复杂链表的函数。在链表中,每个节点除了有一个next指针指向下一个节点,还有一个random指针指向链表中任意节点或者null

示例:

复杂链表

1
2
输入:head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出:[[7,null],[13,0],[11,4],[10,2],[1,0]]

分析

但看这个输入输出,我们可以发现,这看上去是一个二维数组。其中作为元素项的数组组成如[节点的值, 随机指向的节点的序号],在基础的链表上添加了一个随机指向的指针,指向链表中某一个节点的序号或null

复制复杂链表解决的问题其实就是random属性的处理,我们到底是要在创建链表时就添加random还是创建完链表再次遍历添加random。

原地复制再拆分

思路是在原来的链表节点后复制一个新节点,然后再添加指向,最后再将新建的节点拆分出来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
* // Definition for a Node.
* function Node(val, next, random) {
* this.val = val;
* this.next = next;
* this.random = random;
* };
*/

/**
* @param {Node} head
* @return {Node}
*/
var copyRandomList = function(head) {

if (!head) return null

for(let node = head, copy = null; node; node = node.next.next) {
// 遍历新建节点,先复制node节点的值在复制next,最后接到node后边
copy = new Node(node.val)
copy.next = node.next
node.next = copy
}
for(let node = head; node; node = node.next.next) {
// 添加random,node复制出来的random应该指向node.random的复制
if(node.random) {
node.next.random = node.random.next
}
}
let newHead = head.next
for(let node = head, temp = null; node && node.next;) {
//
temp = node.next
node.next = temp.next
node = temp
}
return newHead
};

算法过程图解:

复杂链表的深拷贝

遍历一遍链表,在每个节点后生成新的节点,时间复杂度为O(n),添加random时,链表长度翻倍,时间复杂度为O(2n),拆分链表时又遍历一次长链表,时间复杂度为O(2n),所以总的时间复杂度应该为O(5n)。

新建一个链表,再加几个临时变量,空间复杂度大约为O(n)。

使用Map

将所有的节点存放到Map中,生成node => newNode的映射,然后再迭代生成新链表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
* // Definition for a Node.
* function Node(val, next, random) {
* this.val = val;
* this.next = next;
* this.random = random;
* };
*/

/**
* @param {Node} head
* @return {Node}
*/
var copyRandomList = function(head) {
if(!head) return null
let node = head, list = new Map()
while(node) {
list.set(node, new Node(node.val))
node = node.next
}
let newNode = head
while(newNode) {
list.get(newNode).next = newNode.next ? list.get(newNode.next) : null
list.get(newNode).random = newNode.random ? list.get(newNode.random) : null
newNode = newNode.next
}

return list.get(head)
}

遍历链表一次生成map,再遍历一次map生成链表,时间复杂度O(2n),比原地复制少一点。

但是在空间复杂度上,由于多创建了一个map,空间复杂度为O(2n),比第一种方法略多。

欢迎关注公众号
扫码关注我的微信公众号-大前端合集
  • 微信公众号-大前端合集