-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathproblem-6-union-and-intersection.py
134 lines (105 loc) · 3.28 KB
/
problem-6-union-and-intersection.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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
class Node:
def __init__(self, value):
self.value = value
self.next = None
def __repr__(self):
return str(self.value)
class LinkedList:
def __init__(self):
self.head = None
def __str__(self):
cur_head = self.head
out_string = ""
while cur_head:
out_string += str(cur_head.value) + " -> "
cur_head = cur_head.next
return out_string
def append(self, value):
if self.head is None:
self.head = Node(value)
return
node = self.head
while node.next:
node = node.next
node.next = Node(value)
def size(self):
size = 0
node = self.head
while node:
size += 1
node = node.next
return size
def intersection(llist_1, llist_2):
# Your Solution Here
intersection_lst = LinkedList()
node1 = llist_1.head
tmp_lst = []
while node1 != None:
node2 = llist_2.head
while node2 != None:
if node1.value == node2.value:
if node1.value not in tmp_lst:
tmp_lst.append(node1.value)
#print(node1.value, node2.value)
node2 = node2.next
node1 = node1.next
for i in tmp_lst:
intersection_lst.append(i)
return intersection_lst
def union(llist_1, llist_2):
# Your Solution Here
union_lst = LinkedList()
tmp_lst = []
node1 = llist_1.head
node2 = llist_2.head
while node1 != None:
if node1.value not in tmp_lst:
tmp_lst.append(node1.value)
node1 = node1.next
while node2 != None:
if node2.value not in tmp_lst:
tmp_lst.append(node2.value)
node2 = node2.next
for i in tmp_lst:
union_lst.append(i)
return union_lst
# Test case 1
linked_list_1 = LinkedList()
linked_list_2 = LinkedList()
element_1 = [3,2,4,35,6,65,6,4,3,21]
element_2 = [6,32,4,9,6,1,11,21,1]
for i in element_1:
linked_list_1.append(i)
for i in element_2:
linked_list_2.append(i)
print (union(linked_list_1,linked_list_2))
print (intersection(linked_list_1,linked_list_2))
# Test case 2
linked_list_3 = LinkedList()
linked_list_4 = LinkedList()
element_1 = [3,2,4,35,6,65,6,4,3,23]
element_2 = [1,7,8,9,11,21,1]
for i in element_1:
linked_list_3.append(i)
for i in element_2:
linked_list_4.append(i)
print (union(linked_list_3,linked_list_4))
print (intersection(linked_list_3,linked_list_4))
# Test case 3: empty link
linked_list_5 = LinkedList()
linked_list_6 = LinkedList()
print(union(linked_list_5, linked_list_6))#print empty list
print(intersection(linked_list_5, linked_list_6))#prints empty list
# Test case 4: one empty, and one non-empty linked lists
linked_list_7 = LinkedList()
linked_list_8 = LinkedList()
for i in [1,2,3,4,5,6,7]:
linked_list_7.append(i)
print(union(linked_list_7, linked_list_8))
print(intersection(linked_list_7, linked_list_8))
# Test case 5: a list and itself
linked_list_9 = LinkedList()
for i in [1,2,3,4,5,6,7]:
linked_list_9.append(i)
print(union(linked_list_9, linked_list_9))#prints 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 ->
print(intersection(linked_list_9, linked_list_9))#1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 ->