Copy List with Random Pointer

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.

Solution:

The solution is very similar to Problem Clone Graph. Deep copy vertices first, then copy the edges.

# Definition for singly-linked list with a random pointer.
# class RandomListNode(object):
#     def __init__(self, x):
#         self.label = x
#         self.next = None
#         self.random = None

class Solution(object):
    def copyRandomList(self, head):
        """
        :type head: RandomListNode
        :rtype: RandomListNode
        """

        if head == None:
            return head

        visited = {head: RandomListNode(head.label)}
        q = [head]

        # copy nodes
        while q:
            newQ = []
            while q:
                node = q.pop(0)
                if node.next != None and node.next not in visited:
                    visited[node.next] = RandomListNode(node.next.label)
                    newQ.append(node.next)
                if node.random != None and node.random not in visited:
                    visited[node.random] = RandomListNode(node.random.label)
                    newQ.append(node.random)
            q = newQ

        # copy next and random relationship
        for key in visited:
            # (copied node).next = copied node.next
            if key.next != None:
                visited[key].next = visited[key.next]
            if key.random != None:
                visited[key].random = visited[key.random]

        return visited[head]