LintCode Q105 Copy List with Random Pointer in Python

  • Jinhai ZHOU
  • 4 Minutes
  • 2017年1月17日
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# Definition for singly-linked list with a random pointer.
# class RandomListNode:
# def __init__(self, x):
# self.label = x
# self.next = None
# self.random = None
class Solution:
# @param head: A RandomListNode
# @return: A RandomListNode
def copyRandomList(self, head):
# write your code here
# solution in O(n) space Hash Map
if head is None:
return None
new_head = RandomListNode(head.label)
hash_map = {head: new_head}
new_previous = new_head
current = head.next
while current:
new_current = RandomListNode(current.label)
new_previous.next = new_current
new_previous = new_current
hash_map[current] = new_current
current = current.next
current = head
while current:
new_current = hash_map[current]
if current.random is not None:
new_current.random = hash_map[current.random]
current = current.next
return new_head
知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。