Leetcode 138: Copy List with Random Pointer

 

Code

# 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 is None:
            return None
        
        # store copied nodes indexed by label
        copynodes = dict()
        copyhead = RandomListNode(head.label)
        head_bak = head
        copyhead_bak = copyhead
        
        # copy 'next' for each node
        while head.next:
            copyhead.next = RandomListNode(head.next.label)
            copynodes[head.next.label] = copyhead.next
            copyhead = copyhead.next
            head = head.next

        copyhead = copyhead_bak
        head = head_bak

        # copy 'random' for each node
        while head:
            if head.random:
                copyhead.random = copynodes[head.random.label]
            head = head.next
            copyhead = copyhead.next

        return copyhead_bak

 

Idea

Two rounds copy. In the first round, make sure node is copied and connected one by one. During the first round, also record newly copied nodes in a dictionary copynodes. In the second round, copy field random. You need to use the dictionary to locate the new copied nodes in constant time.

Note: This algorithm only works when no two nodes have the same label because we use node.label as keys in the dictionary.

 

More elegant way to utilize defaultdict:

# 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

from collections import defaultdict
class Solution(object):
    def copyRandomList(self, head):
        """
        :type head: RandomListNode
        :rtype: RandomListNode
        """
        d = defaultdict(lambda: RandomListNode(0))
        d[None] = None
        tmp = head
        while tmp:
            d[tmp].label = tmp.label
            d[tmp].next = d[tmp.next]
            d[tmp].random = d[tmp.random]
            tmp = tmp.next
        return d[head]

 

Idea

d is a defaultdict. The key of d is original node and the value is the copied node.

 

Reference: https://discuss.leetcode.com/topic/5954/my-short-python-solution-with-o-n-complex-using-collections-defaultdict

 

Another very convoluted way to solve this problem. Only constant extra space will be used: https://discuss.leetcode.com/topic/7594/a-solution-with-constant-space-complexity-o-1-and-linear-time-complexity-o-n/2