Copy Linked List With Random Pointer

Question Description

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

Two pass to solve this question.

First Pass: get a deep copy of all the next pointers and construct a hash table of original node to copied node.

Second Pass: connect all the random pointers of the copied linked list.

class Solution(object):
    def copyRandomList(self, head):
        """
        :type head: RandomListNode
        :rtype: RandomListNode
        """
        rdn, newhead, cur, newcur = {}, None, head, None
        while cur:
            if not newhead:
                newcur = RandomListNode(cur.label)
                newhead = newcur
            else:
                newcur.next = RandomListNode(cur.label)
                newcur = newcur.next
            rdn[cur] = newcur
            cur = cur.next
        cur, newcur = head, newhead
        while cur:
            if cur.random:
                newcur.random = rdn[cur.random]
            cur = cur.next
            newcur = newcur.next
        return newhead