def copyRandomList(self, head):
"""
:type head: Node
:rtype: Node
"""
if not head:
return head
dummy = Node(-1,None,None)
copycur = dummy
cur = head
copymap = {}
while cur:
if cur not in copymap.keys():
node = Node(cur.val, None, None)
copymap[cur] = node
# 注意cur.random為空的時候不要插入到copymap中
if cur.random and cur.random not in copymap:
node = Node(cur.random.val, None, None)
copymap[cur.random] = node
copycur.next = copymap[cur]
copycur = copycur.next
# 注意cur.random為空的時候copymap中查不到對應(yīng)的value
if not cur.random:
copycur.random = None
else:
copycur.random = copymap[cur.random]
cur = cur.next
return dummy.next
def copyRandomList(self, head):
"""
:type head: Node
:rtype: Node
"""
if not head:
return head
# 第一輪,copy所有node
cur = head
while cur:
node = Node(cur.val, None, None)
last = cur.next
cur.next = node
node.next = last
cur = last
# 第二輪,完成random指針
cur = head
while cur:
if cur.random:
cur.next.random = cur.random.next
else:
cur.next.random = None
cur = cur.next.next
# 第三輪,把鏈表拆開
cur = head
dummy = Node(-1, None, Node)
curcopy = dummy
while cur:
curcopy.next = cur.next
last = cur.next.next
cur.next = last
curcopy = curcopy.next
curcopy.next = None
cur = last
return dummy.next
