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]
