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).