Copy List With Random Pointer

The problem

You are given head, the first node of a linked list. Each node holds a value, val, and two links that may be null: next, to the node after it, and random, to any node of the list, even itself. Return the first node of a deep copy: new nodes with the same values in the same order, whose next and random links point at the matching new nodes. No link of the copy may lead to an original node, and the original must stay unchanged. For an empty list, given as null, return null. The examples show each node as [value, position of its random node], counting from 0.

What to write

Implement solve using the node objects described above. The judge constructs the objects from the serialized examples.

type RandomNode = {val:number;next:RandomNode|null;random:RandomNode|null};

function solve(head: RandomNode | null): RandomNode | null

Input
nodes = [[7,null],[13,0],[11,4],[10,2],[1,0]]

Output
[[7,null],[13,0],[11,4],[10,2],[1,0]]

Input
nodes = [[1,0]]

Output
[[1,0]]

Constraints

0 ≤ node count ≤ 1000.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   A random link can point backward, forward or at its own node. So when you reach a node, the node its random link points at may not have been visited yet. Two nodes can also hold the same value, so a value does not tell you which node you have.

2. Hint 2: Ask a smaller question

   In the first example the node 13 has a random link to the node 7. Suppose new nodes for 7 and for 13 already exist. To set the random link of the new 13, what do you have to be able to find, starting from the original 7?

3. Hint 3: Name the pattern

   Every link asks the same question: which new node stands for this original node? Store the answer for every node in a hash map from original node to copy, and each link is one lookup away. Getting from one thing to its partner in one step is a hash map lookup. Read the lesson on hash map lookup.

4. Hint 4: State the invariant

   After the first walk, the map holds every original node together with its own new copy. So wherever a link of an original node points, the matching link of its copy is the map's entry for that target.

5. Hint 5: Sketch the pseudocode

   Make an empty map. Walk the list: for each node, create a new node with the same value and store it under the original node. Walk again: set each copy's next and random to the map's entries for the original's next and random, keeping null as null. Return the entry for head, or null for an empty list.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Allocate one new node per original node, then rebuild both pointer types through an original-to-copy map.

The slow way

Copy the nodes along next first. Then, for each random link, walk the original from the head to count how far its target is, and walk the copy the same distance to find the matching new node. It is correct, but every link can cost a walk over both lists: up to about 2 × n × n steps for n nodes.

The insight

The whole difficulty is one question, asked for every link: which new node stands for this original node? A hash map, a table that finds the entry for a key in about one step, can hold the answer for every node. Then it no longer matters where a link points.

Step by step

1. Keep a map from each original node to its copy. The map answers "which new node stands for this one?" in about one step. Its key is the node itself, not the value, because two nodes can hold the same value.
2. First walk: make a copy of every node, with no links yet. A random link can point at a node further along the list. Making all the copies before setting any link means the copy a link needs always exists already.
3. Second walk: a copy's next is the copy of the original's next. A copy must not link to an original node. The link is translated through the map: look up the node the original points at and use its copy. The last node points at nothing, so its copy's link is null.
4. A copy's random is the copy of the original's random. It is the same translation. Every copy exists by now, so it works whether the link points backward, forward or at the node itself, and a null link stays null.
5. The answer is the copy of the first node. The copy of the first node leads to all the other copies. An empty list has no first node, so there is nothing to look up and the answer is null.

The same numbered steps are the comments in each solution.

function solve(head) {
  // 1. Keep a map from each original node to its copy
  const copies = new Map();
  // 2. First walk: make a copy of every node, with no links yet
  for (let n = head; n; n = n.next)
    copies.set(n, { val: n.val, next: null, random: null });
  // 3. Second walk: a copy's next is the copy of the original's next
  for (let n = head; n; n = n.next) {
    const copy = copies.get(n);
    copy.next = n.next ? copies.get(n.next) : null;
    // 4. A copy's random is the copy of the original's random
    copy.random = n.random ? copies.get(n.random) : null;
  }
  // 5. The answer is the copy of the first node
  return head ? copies.get(head) : null;
}

type RandomNode = {
  val: number;
  next: RandomNode | null;
  random: RandomNode | null;
};
function solve(head: RandomNode | null): RandomNode | null {
  // 1. Keep a map from each original node to its copy
  const copies = new Map<RandomNode, RandomNode>();
  // 2. First walk: make a copy of every node, with no links yet
  for (let n = head; n; n = n.next)
    copies.set(n, { val: n.val, next: null, random: null });
  // 3. Second walk: a copy's next is the copy of the original's next
  for (let n = head; n; n = n.next) {
    const copy = copies.get(n)!;
    copy.next = n.next ? copies.get(n.next)! : null;
    // 4. A copy's random is the copy of the original's random
    copy.random = n.random ? copies.get(n.random)! : null;
  }
  // 5. The answer is the copy of the first node
  return head ? copies.get(head)! : null;
}

def solve(head):
    # 1. Keep a map from each original node to its copy
    copies = {}
    # 2. First walk: make a copy of every node, with no links yet
    node = head
    while node:
        copies[node] = RandomNode(node.val)
        node = node.next
    # 3. Second walk: a copy's next is the copy of the original's next
    node = head
    while node:
        # A link that is None has no copy: .get(None) finds nothing and gives None.
        copies[node].next = copies.get(node.next)
        # 4. A copy's random is the copy of the original's random
        copies[node].random = copies.get(node.random)
        node = node.next
    # 5. The answer is the copy of the first node
    return copies.get(head)

Example 1, traced

Input
nodes = [[7,null],[13,0],[11,4],[10,2],[1,0]]

Output
[[7,null],[13,0],[11,4],[10,2],[1,0]]

Why it works

After the first walk every original node has exactly one copy, recorded in the map. The second walk gives each copy the two links of its original, translated through the map. So the copies are linked to one another in the same shape as the originals, and no link leaves the copy. The original is only read.

Time and space

Time O(n), extra space O(n). The list is walked twice, and each node costs a fixed number of map operations of about one step each, so the time is O(n). The map holds one entry per node and the copy has n new nodes, so the space is O(n).

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Do not copy a link as it is. A next or random taken straight from the original points at an original node, and the checker rejects an answer that leads back into the input.
• Make every copy before you set a random link. In a single pass, a link that points forward finds no copy yet: in the first example the copy of 11 would lose its link to 1.
• Key the map by the node, not by its value: two nodes can hold the same value and would share one entry. In JavaScript use a Map, because a plain object turns every node into the same key.

Pattern

Hash map lookup. Builds on Two Sum and Reverse Linked List.

Keep going