Copy List with Random Pointer

Patrick Leaton
Published: Nov. 6, 2021, 3:39 p.m.
Problem Description

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

Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list.

For example, if there are two nodes X and Y in the original list, where X.random --> Y, then for the corresponding two nodes x and y in the copied list, x.random --> y.

Return the head of the copied linked list.

The linked list is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:

  • val: an integer representing Node.val
  • random_index: the index of the node (range from 0 to n-1) that the random pointer points to, or null if it does not point to any node.

Your code will only be given the head of the original linked list.

 

Example 1:

Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

Example 2:

Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]

Example 3:

Input: head = [[3,null],[3,0],[3,null]]
Output: [[3,null],[3,0],[3,null]]

Example 4:

Input: head = []
Output: []
Explanation: The given linked list is empty (null pointer), so return null.

 

Constraints:

  • 0 <= n <= 1000
  • -10000 <= Node.val <= 10000
  • Node.random is null or is pointing to some node in the linked list.

 

The description was taken from https://leetcode.com/problems/copy-list-with-random-pointer/.

Problem Solution

#DFS
#O(N) Time, O(N) Space
class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        seen = {}
       
        def dfs(node: Node) -> Node:
            if not node:
                return None
            node_copy = Node(node.val)
            seen[node] = node_copy
            if node.random not in seen:
                node_copy.random = dfs(node.random)
            else:
                node_copy.random = seen[node.random]
            if node.next not in seen:
                node_copy.next = dfs(node.next)
            else:
                node_copy.next = seen[node.next]
            return node_copy
       
        return dfs(head)
 
#Iterative
#O(N) Time, O(1) Space
class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        if not head:
            return head
 
        old = head
        while old:
            new = Node(old.val)
            new.next = old.next
            old.next = new
            old = new.next

        old = head
        while old:
            if old.random:
                old.next.random = old.random.next
            old = old.next.next
 
        dummy = Node(-1)
        new = dummy
        old = head
        while old:
            new.next = old.next
            new = new.next
            old = old.next.next

        return dummy.next

Problem Explanation

Depth-First Search

This solution has the same idea as Clone Graph.

The main idea is that if we want to create a node and set a pointer to another node, we would first need to make sure that we have created that second node first in order to set the pointer.

To check for this, we can make a HashMap where we can reference which nodes have been created thus far.  We will utilize the original node as the hash key and the copied node as the hash value.

To solve this problem, we can perform a DFS on each node to make a copy, place the copy in the dictionary, and if we see that our copy's random or next node has not been created yet then we will halt and perform a DFS on these nodes to create them before we set the pointers.

Let's start by initializing our dictionary of nodes that we have seen and created.

        seen = {}

Next, we will create a DFS function that will take a node from the original list and return a copy of the node.

        def dfs(node: Node) -> Node:

 

If the input node is null, then we will return null.  

This is for the tail of the original list and also for random pointers from the original list's nods that are null.

            if not node:
                return None

 

Otherwise, we will create a node copy and mark the original node as seen, mapping the copy to it.

One thing to note here is that the problem input is somewhat confusing.  For example, the input shows node eleven has a random pointer to node four.  What it probably should be here instead is node two has a random pointer to node four, or node eleven has a random pointer to node one.

It is because of this that we have to use the nodes themselves at the hashing keys and not their values.

            node_copy = Node(node.val)
            seen[node] = node_copy

 

Before setting our node copy's random pointer, we will first need to make sure we have created the node we're about to point it to.

If the original node's random pointer has not been seen yet, then we have not created a copy for it.

If that is the case, we will perform a DFS on the original node's random pointer so we can create it before making a copy.

            if node.random not in seen:
                node_copy.random = dfs(node.random)

 

If we have created it, then we will set our node copy's random pointer to the copy of the original random node's copy.

            else:
                node_copy.random = seen[node.random]

 

We will do the same thing for the copy's next pointer.

            if node.next not in seen:
                node_copy.next = dfs(node.next)
            else:
                node_copy.next = seen[node.next]

 

Once we have set both pointers, we will return the node.

            return node_copy

After we have finished making our DFS function, we will need to start our DFS on the head.

This will return the head of the new list once each node within the list has been copied.

        return dfs(head)

Iterative Constant Space

This solution is much more difficult but will allow us to reference random pointers in constant time without caching nodes.

We can do this by placing each copied node directly after each original node.

1->1->2->2->3->3->None

By doing this, we can traverse each original node where the copied node comes directly thereafter.  If we want to know which node to set the copied node's random pointer to then we can immediately refer to the node directly after the original node's random pointer.

To solve this problem, we can interweave the original and copied nodes as shown above, then update the random pointers of each copied node by utilizing the previous, original node's random pointers, then we will need to break the interweaved list into two separate lists. 

First off, if the head is null then we have no list to copy.

        if not head:
            return head

 

Otherwise, we will start by interweaving our list.

We will set our old node pointer to the head of the list and continue traversing down the original list.

        old = head
        while old:

 

We'll create a new node with the old node's value.

            new = Node(old.val)
 

We will set its next pointer to the old pointer's next node, then we will set the old node's next pointer to the new node.

             new.next = old.next
            old.next = new

 

After, we will step to the new node's next pointer, which will be the old node's previous next pointer prior to changing.

            old = new.next

 

Once we have finished interweaving the two lists, we will set the old node pointer back to the head of the old list.

        old = head

 

Next, we will set the random pointers for each copied node.

While we still have nodes to traverse in the old list, we will continue setting random pointers.

        while old:
 

if the current old node has a random pointer, then its copy will be directly after it within the interweaved list.

If the old node has a random pointer, then we will set the new node's random pointer to the node directly after the old node's random.

            if old.random:
                old.next.random = old.random.next

 

Once we do that, we will step to the next original node.

            old = old.next.next

 

Now we will need to build the new list and restore the old list.

We will start by setting a dummy node for the new list and setting a new pointer to it.

        dummy = Node(-1)
        new = dummy

 

Let's also make a pointer for the old list at the head of the current list.

        old = head

 

While we still have nodes to traverse in the old list, we will continue building and restoring.

        while old:

 

We will set the next node in the new list as the node directly after the old node.

We will then iterate the new node pointer to the newly added tail of its list, and the old node to the next original node which is directly after the clone that is in front of it.

            new.next = old.next
            new = new.next
            old = old.next.next

 

When we have finished building the new list and restoring the old one, we will return the new head which will be the node directly after the dummy.

        return dummy.next