給你一個長度為 n 的鏈表瓢剿，每個節(jié)點包含一個 next 指針和一個random 指針额划，random 指針可以指向鏈表中的任何節(jié)點或空節(jié)點渴逻。構(gòu)造這個鏈表的深拷貝疾党，新鏈表由 n 個全新節(jié)點組成，復(fù)制鏈表的指針不應(yīng)指向原鏈表中的節(jié)點惨奕。
遍歷
用map留存克隆過的數(shù)組雪位，然后進行遍歷
- 時間復(fù)雜度O(n)，空間復(fù)雜度O(1)
- Runtime: 84 ms, faster than 47.37%
- Memory Usage: 40.7 MB, less than 19.00%
/**
* // Definition for a Node.
* function Node(val, next, random) {
* this.val = val;
* this.next = next;
* this.random = random;
* };
*/
/**
* @param {Node} head
* @return {Node}
*/
var map = new Map()
var copyRandomList = function(head) {
if(head === null) return null
let copy = new Node(head.val)
map.set(head, copy)
let p = head
while(head !== null) {
copy.next = getCloneNode(head.next)
copy.random = getCloneNode(head.random)
copy = copy.next
head = head.next
}
return map.get(p)
};
var getCloneNode = function(node) {
if(node === null) return null
if(!map.has(node)) {
map.set(node, new Node(node.val, null, null))
}
return map.get(node)
}
