Copy List with Random Pointer

Intuition

• In order to correctly create a deep copy, you need to keep track of the nodes that are random without directly copying that node.
• Similar to Two Sum, you can do this by hashing the nodes such that the random node pointed to maps to the corresponding node created in the first iteration of the deep copy.
• The point here is that you first need to create all those nodes in order to have something to point to.

Runtime and Space

• $O(N+N)=O(N)$ runtime due to having to traverse linked list twice
• $O(N)$ extra space due to having to store N slots for the hash map conversion

Code

Cleaned up Using Dummy Pointer

"""
# 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
"""
 
class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        root = Node(-1)
        cur = root
        itr = head
        hm = {}
 
        while itr:
            cur.next = Node(itr.val)
            cur = cur.next
            hm[itr] = cur 
            itr = itr.next
        
        cur = root
        itr = head
        while itr:
            if itr.random:
                cur.next.random = hm[itr.random]
            cur = cur.next
            itr = itr.next
 
        return root.next

Without Dummy Pointer

"""
# 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
"""
 
class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if not head:
            return None
 
        root = Node(head.val)
        node = root
        itr = head
        hmap = {head: root}
        while itr.next:
            node.next = Node(itr.next.val)
            itr = itr.next
            node = node.next
            hmap[itr] = node
 
        node = root
        if head.random:
            root.random = hmap[head.random]
        itr = head
        while itr.next:
            if itr.next.random:
                node.next.random = hmap[itr.next.random]
            itr = itr.next
            node = node.next
        
        return root

Notes

---

References

https://leetcode.com/problems/copy-list-with-random-pointer/