Copy List with Random Pointer

hard, linked list

Question

构建链列，其中每个节点多包含一个随机指针指向链列中的任意节点（也可以是null)。如下图：

Solution

构建map/dictionary。

# 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
        """
        dic = dict()
        dic[None]=None
        p = head
        dummy = RandomListNode(0)
        q = dummy
        while p:
            q.next = RandomListNode(p.label)
            dic[p] = q.next
            p = p.next
            q = q.next
        p = head
        q = dummy
        while p:
            q.next.random = dic[p.random]
            p = p.next
            q = q.next
        return dummy.next

以上需要使用额外的space O(n), 可以进一步降低存储要求。建立每个node的一个copy, 使原node指向它的copy

# 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
        """
        import collections
        dic = collections.defaultdict(lambda: RandomListNode(0))
        dic[None] = None
        node = head
        while node:
            dic[node].label = node.label
            dic[node].next = dic[node.next]
            dic[node].random = dic[node.random]
            node = node.next
        return dic[head]