138. Copy List with Random Pointer

Problem

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

Solution

/** * Definition for singly-linked list with a random pointer. * function RandomListNode(label) { * this.label = label; * this.next = this.random = null; * } */ /** * @param {RandomListNode} head * @return {RandomListNode} */ var copyRandomList = function(head) { if (!head) return null; var map = new Map(); var now = null; now = head; while (now) { map.set(now, new RandomListNode(now.label)); now = now.next; } now = head; while (now) { map.get(now).next = map.get(now.next) || null; map.get(now).random = map.get(now.random) || null; now = now.next; } return map.get(head); }; 

Explain:

ES6 的 Map 可以用任意类型的 key。如果用 label 做 key 的话，可能重复，直接 object 做 key 就好。

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).