138-复制带随机指针的链表

138. 复制带随机指针的链表

拿到题目的想法是使用双指针指向新旧节点,再加上一个 map 用来映射旧节点和新节点。

递归

1
2
3
4
5
6
7
8
9
10
11
12
var listMap = new Map()
var copyRandomList = function(head) {
if(head === null) return head
if (listMap.get(head)) {
return listMap.get(head)
}
let newNode = new Node(head.val,null,null)
listMap.set(head, newNode)
newNode.next = copyRandomList(head.next)
newNode.random = copyRandomList(head.random)
return newNode
};

迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var copyRandomList = function(head) {
if(head == null) return head
var listMap = new Map()
listMap.set(null,null)
var cur = head
while (cur!= null) {
listMap.set(cur,new Node(cur.val,null,null))
cur = cur.next
}
cur = head
while (cur!= null) {
listMap.get(cur).next = listMap.get(cur.next)
listMap.get(cur).random = listMap.get(cur.random)
cur = cur.next
}
return listMap.get(head)
};