Copy List with Random Pointer

Problem: Copy List with Random Pointer

It's easy to use iteration to deep copy a normal linked list. The difficulty lies in random pointers. It's possible that while copying a node, its random pointer points to a non-existing node in our result. Thus, we need to create it, which means it can interfere the node we create in a simple copying. When we are creating a node, to avoid conflict and solve non-existence, we need to check it with history to decide whether we shall create a new one or using an existing one. The history can be maintained as a hash table.

Code in Python:

class Solution(object):
    def copyRandomList(self, head):
        """
        :type head: RandomListNode
        :rtype: RandomListNode
        """
        ptr, prev, dict = head, None, {}
        while ptr:
            if ptr.label not in dict:
                newNode = RandomListNode(ptr.label)
                dict[ptr.label] = newNode
            if prev: prev.next = dict[ptr.label]
            if ptr.random:
                if ptr.random.label not in dict:
                    randomNode = RandomListNode(ptr.random.label)
                    dict[ptr.random.label] = randomNode
                dict[ptr.label].random = dict[ptr.random.label]
            prev, ptr = dict[ptr.label], ptr.next
        return dict[head.label] if head else None