Creating a Deepcopy of Linkedlist with random pointers

While solving a Leetcode problem yesterday I came across this pretty cool problem which is fairly very different then most that I have solved. Here we have to create a deep copy of a linked list which also has random pointers which can point to any other random node in the linked list or None.
Feel free to have a try yourself here 138. Copy List with Random Pointer

A little weird problem here, firstly to clear some confusions, deep copy means a separate copy in the memory, basically if anything was to happen to the original list nothing would happed to the deep copy as that is a completely independent copy of the list.

So to make a deep copy we will have to make brand new nodes and use the relationships in the original linked list to be properly mapped to the new ones.

Coming to the random pointers, that means that every node in the linked list has a new variable apart from the usual value and next which is random which can be pointing to any random node in the linked list or None.

The best way to approach this problem is to first create a copy of all the nodes in the original lineked list and then use the original linked list to create all the connections or basically assign all the pointers.

Now the first thing that might come to mind is just creating copies of the node using the Vals, of the original list, but how do you keep track of them, as without the pointers to the next node they might just get lost in the memories, we need to hold them somewhere.

Also, to assign the pointer values to the new linked list we will need to access the values from the original linkedlist, and as we know finding a node in linked list takes O(n) which is not the best. So, what the best solution in this case might be is to use a hash map, as that can help us store our new nodes without pointers as well as we can map the old nodes to the new ones while having a constant O(1) time to look up values or nodes in this case.

here goes nothing:

#there already exists a Node class that only takes `x` as the input to create a new node.
#but also has 'random' and 'next' pointers to set.

def deepCopy(head):
    hmap = {}
    dummy_pointer = head

    while dummy_pointer:
        new_node = Node(dummy_pointer.val)    # In the origianl Llist, the x is represented as val
        hmap[dummy_pointer] = new_node
        dummy_pointer = dummy_pointer.next

    dummy_pointer = head


    while dummy_pointer:
        curr_new_node = hmap[dummy_pointer]

        curr_new_node.next = hmap[dummy_pointer.next] if dummy_pointer.next else None
        curr_new_node.random = hmap[dummy_pointer.random] if dummy_pointer.random else None
        dummy_pointer = dummy_pointer.next


    return hmap[head]

Now this might look like all, but there is an edge case that we also need to take care of, which is what if the original linkedlist is empty. Pretty straightforward just have a conditional in the beginning to check if the incoming Llist is empty if it is just return None.

#there already exists a Node class that only takes `x` as the input to create a new node.
#but also has 'random' and 'next' pointers to set.

def deepCopy(head):
    if head == None: return None
    hmap = {}
    dummy_pointer = head

    while dummy_pointer:
        new_node = Node(dummy_pointer.val)    # In the origianl Llist, the x is represented as val
        hmap[dummy_pointer] = new_node
        dummy_pointer = dummy_pointer.next

    dummy_pointer = head


    while dummy_pointer:
        curr_new_node = hmap[dummy_pointer]

        curr_new_node.next = hmap[dummy_pointer.next] if dummy_pointer.next else None
        curr_new_node.random = hmap[dummy_pointer.random] if dummy_pointer.random else None
        dummy_pointer = dummy_pointer.next


    return hmap[head]