-
Notifications
You must be signed in to change notification settings - Fork 0
/
clone_random_list.py
82 lines (72 loc) · 2.08 KB
/
clone_random_list.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
from random import randint
class Node():
def __init__(self, data):
self.data = data
self.next = None
self.random = None
class LinkedList:
def __init__(self):
self.head = None
self.counter = 0
def push(self, data):
node = Node(data)
self.counter += 1
if not self.head:
self.head = node
else:
node.next = self.head
self.head = node
val = randint(1, self.counter)
state = 1
current = self.head
while current is not None:
if state == val:
self.head.random = current
state += 1
current = current.next
def display(self, pattern='next'):
if pattern == 'next' or pattern == 'random':
current = self.head
while current is not None:
print(current.data, "->", current.random.data)
# current = getattr(current,pattern)
current = current.next
else:
print("Only two patterns available: next and random")
def clone_list(head):
if head is None:
return None
else:
current = head
while current is not None:
node = Node(current.data)
node.next = current.random
current.random = node
current = current.next
current = head
while current is not None:
node = current.random
node.random = node.next.random
if current.next:
node.next = current.next.random
else:
node.next = None
current = current.next
return head.random
if __name__ == '__main__':
ll = LinkedList()
n = int(raw_input())
while n:
d = int(raw_input())
ll.push(d)
n -= 1
print("Display by next")
ll.display()
# print("Display by random")
# ll.display('random')
ll2 = LinkedList()
ll2.head = clone_list(ll.head)
print("Display 2 by next")
ll2.display()
# print("Display 2 by random")
# ll2.display('random')