Medium

Copy List with Random Pointer

049

Given nodes encoded as [value, randomIndex], return a deep-copied encoding with the same values and random links.

EXAMPLES

Example 1

Input
{
  "nodes": [
    [
      7,
      -1
    ],
    [
      13,
      0
    ],
    [
      11,
      4
    ],
    [
      10,
      2
    ],
    [
      1,
      0
    ]
  ]
}

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

FUNCTION SHAPE

nodes: intMatrix→intMatrix

SOLUTION NOTE

You can't just copy the list naively, because how do you copy the random pointers? You need a map between old nodes and new nodes in order to point the random pointers to the correct new node.

The idea is simple, we maintain an old to new node map. We first iterate over the old nodes, creating new nodes and setting the .next pointers of the new nodes, and updating the map.

Once the map is filled, we can fill in the random nodes. We iterate over the old nodes again, and if there is a random pointer, we set the new nodes random pointer to the new node that corresponds to the old nodes random node.

Note there is another solution that involves interleaving, but it is more complex. This solution is generic to the copy graph problem as well involving BFS so I recommend learning this.

Reveal reference solution +

pythonREFERENCE

"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""

# KEY IDEA: use map between nodes in the original list and nodes in the
# copied list for fast O(1) setting of random ptrs
# O(n) time, O(n) space

# step 1. copy the new linked list with only values and next ptrs
# step 2. fill in the random pointers for the new linked list

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if not head: return head
        old_to_new_map = {}
        og_head = head
        prev_new_node = None
        curr_old_node = head

        while curr_old_node:
            new_node = Node(curr_old_node.val)
            if prev_new_node:
                prev_new_node.next = new_node
            prev_new_node = new_node
            old_to_new_map[curr_old_node] = new_node
            curr_old_node = curr_old_node.next

        # fill in random nodes now
        curr_old_node = og_head
        while curr_old_node:
            if curr_old_node.random:
                old_to_new_map[curr_old_node].random = old_to_new_map[curr_old_node.random]
            curr_old_node = curr_old_node.next

        return old_to_new_map[og_head]

TimeO(n)

SpaceO(n)

Open on LeetCode ↗