[Top Interview 150] 138. Copy List with Random Pointer

Solution)

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        # Base Case
        if not head: return None

        # Checkpoints that will save the heads of each linked list
        original = head
        root = Node(head.val)

        # Dictionary that will save {original node : copied node}
        # Those paired nodes have the same value.
        dic = {head:root}
        
        # Deepcopy each node and link them 
        # without connecting random for now
        start = root
        while head.next:
            start.next = Node(head.next.val)
            dic[head.next] = start.next
            
            start = start.next
            head = head.next
        
        # Now connect the random
        start = root
        while original:
            start.random = dic[original.random] if original.random else None

            start = start.next
            original = original.next
        
        # return deepcopied head
        return root

 
Problem: LeetCode
 
Time Complexity: O(n)
Space Complexity: O(n)
 

Explanation)

We'll need to iterate the original linked list twice.
 
1) create copied nodes and connecting them via next attribute.
2) connect copied nodes via random attribute.
 
To find a copied node that needs to be connected via random attribute, we need an extra space to save those copied nodes during the first iteration. Thus, we'll use a dictionary for that purpose.
 
By saving in a format of {original node : copied node}, we'll easily find the wanted random node.
 
In the second iteration of original linked list, we'll look for the current original node's random node in dictionary, then set the paired copied node to current copied node's random attribute.
 
Let's dive in!

 

Base Case + Initialization)

If head is not given, there's nothing to copy so just return None.
 
Variables original and root will be the checkpoints for us to easily get back to the start of each linked list. So even after we completely iterate the lists, we can go back to the start of the lists using these variables.
 
Dictionary dic will save {original node : copied node} for us to easily get the copied node.
 

def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if not head: return None
        
        original = head
        root = Node(head.val)

        dic = {head:root}

 

First Iteration)

To iterate a linked list, we'll need a separate node variable.
start will iterate copied linked list, and head will iterate original linked list.
 
As we iterate, we'll make a copied node and set it as the current start's next.
Then, we'll save {original node to copied node} pair to dic.
 
This is the main job we need to do in this iteration, so we go on to the next node in the linked lists.
 

def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if not head: return None

        original = head
        root = Node(head.val)

        dic = {head:root}
        
        start = root
        while head.next:
            start.next = Node(head.next.val)
            dic[head.next] = start.next
            
            start = start.next
            head = head.next

 

Second Iteration)

Once we've connect copited nodes via next attribute and saved node pairs to dic, it's time to connect copited nodes via random attribute.
 
The logic is this.
1) We iterate the original linked list.
- while original:
 
2) As we iterate, we'll find the current node's random attribute. 
- original.random
 
3) Once we have the random node, we already know that the random node exists in our dic.
4) We also know that the random node's paired node is a copied node with the same value.
- dic[original.random]
 
5) So, we set that copied node as start's random node.
- start.random = dic[original.random]
 
 
If the second iteration is completed, we have a complete copied linked list, so we return root.
 

def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        # Base Case
        # Initialization
        
        start = root
        while head.next:
            start.next = Node(head.next.val)
            dic[head.next] = start.next
            
            start = start.next
            head = head.next
        
        start = root
        while original:
            start.random = dic[original.random] if original.random else None

            start = start.next
            original = original.next
        
        return root

 
 
 
I thought there might be a better approach than this because it seemed like I was using unnecessary memory, but other solutions also had similar approaches as well. Whenever I solve for linked-list problems, I usually struggle with which nodes to use and update.