-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy List with Random Pointer LC-128.py
100 lines (55 loc) · 1.78 KB
/
Copy List with Random Pointer LC-128.py
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
"""
# Definition for a Node.
class Node:
def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
self.val = int(x)
self.next = next
self.random = random
"""
class Solution:
def copyRandomList(self, head: 'Node') -> 'Node':
if not head:
return
temp=head
while temp:
copy=Node(temp.val)
backup=temp.next
temp.next=copy
copy.next=backup
temp=temp.next.next
temp=head
copy_head=head.next
copy=copy_head
while copy and copy.next:
if temp.random:
copy.random=temp.random.next
else:
copy.random=None
temp=temp.next.next
copy.next=copy.next.next
copy=copy.next
if temp and temp.random:
copy.random=temp.random.next
return copy_head
# Using map
# if not head:
# return
# copy_head = Node(head.val)
# copy=copy_head
# temp=head.next
# map = {head: copy}
# while temp:
# copy.next=Node(temp.val)
# copy=copy.next
# map[temp]=copy
# temp=temp.next
# temp=head
# copy=copy_head
# while temp:
# if not temp.random:
# copy.random=None
# else:
# copy.random=map[temp.random]
# temp=temp.next
# copy=copy.next
# return copy_head