How to deep copy a linked list with a random pointer?

Problem description

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.

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) where random pointer points to, or null if it does not point to any node.

Example:

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

You can solve this problem here: leetcode 138.

Solution

Different from the classic linked list, this abstract data structure has a random pointer points to a node in the list. When iterating the given linked list to create a deep copy, it’s necessary to link the random pointer as well. I’ll introduce two solutions here, one using an extra space, one using O(1) space.

Deep copy the linked list using a dictionary

In order to record the connection of the current node with its next and random node, we can use a dictionary to store the relationship. While iterating over the given linked list, we’ll record the {currentNode: nextNode} into the dictionary, then build the connection in our copied list.

Code:

class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
    def copyRandomList(self, head):
        dic, prev, node = {}, None, head
        while node:
            if node not in dic:
                dic[node] = Node(node.val, node.next, node.random)
            if prev:
                
                prev.next = dic[node]
            else:
                head = dic[node]
            if node.random:
                if node.random not in dic:
                    dic[node.random] = Node(node.random.val, node.random.next, node.random.random)
                #connect the random node
                dic[node].random = dic[node.random]
            prev, node = dic[node], node.next
        return head

This solution will take O(n) running time because it iterates the original linked list once. Since it uses a dictionary with size n to record the relationship, it takes O(n) space.

Deep copy the linked list with O(1) space

What if we are given a linked list with an infinite size n? Having extra space is not ideal. How to solve it without extra space? We can first copy each node and attached it to the current node as the next, then gradually copy the random node using node.next.random = node.random.next. The following picture will explain:

Code:

class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
    def copyRandomList(self, head: 'Node') -> 'Node':
        if not head:
            return None
        
        curr = head
       #copying the next node and link it to the current node
        while curr:
            new_curr = Node(curr.val)
            next_node = curr.next
            curr.next = new_curr
            new_curr.next = next_node
            curr = next_node
        
        curr = head
       #copying the random node 
        while curr:
            if not curr.random:
                curr.next.random = None
            else:
                curr.next.random = curr.random.next
            
            curr = curr.next.next
        curr = head.next
       #break the connection, only left the copy list
        while curr.next:
            next_node = curr.next.next
            curr.next = next_node
            curr = next_node
        
        return head.next

This solution takes O(1) space because it modifies the original list. In terms of the running time, it loops the list 3 times which is 3n, approximately O(n).

Hope you understand how it works to deep copy a list! Which solution do you prefer?