-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathoverlapping_lists.py
More file actions
97 lines (80 loc) · 1.7 KB
/
overlapping_lists.py
File metadata and controls
97 lines (80 loc) · 1.7 KB
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
#Find the meeting point of 2 linked lists
from linkedlist import *
import time
def binary_search(a,b):
pass
head1 = Node(1)
node2 = Node(2)
node3 = Node(3)
node4 = Node(4)
node5 = Node(5)
node6 = Node(6)
node7 = Node(7)
node8 = Node(8)
node9 = Node(9)
head1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5
node5.next = node6
node6.next = node7
node7.next = node8
node8.next = node9
head2 = Node("a")
nodeB = Node("b")
nodeC = Node("c")
head2.next = nodeB
nodeB.next = nodeC
nodeC.next = node5
def find_meeting_point_quadratic(head1, head2):
ptr1 = head1
while(ptr1!= None):
ptr2 = head2
while(ptr2!= None):
if(ptr2 == ptr1):
return ptr2
ptr2 = ptr2.next
ptr1 = ptr1.next
def find_meeting_point2(head1, head2):
ids = []
ptr1 = head1
while(ptr1!= None):
ids.append(id(ptr1))
ptr1 = ptr1.next
ids.sort()
ptr2 = head2
while(ptr2!= None):
if(binary_search(id(ptr2),ids)):
return ptr2
ptr2 = ptr2.next
def find_meeting_point_stacks(head1, head2):
stack1 = []
ptr1 = head1
while(ptr1!= None):
stack1.append(ptr1)
ptr1 = ptr1.next
stack2 = []
ptr2 = head2
while(ptr2!= None):
stack2.append(ptr2)
ptr2 = ptr2.next
ptr1 = stack1.pop()
ptr2 = stack2.pop()
meeting = ptr1
while(ptr1 == ptr2):
meeting = ptr1
ptr1 = stack1.pop()
ptr2 = stack2.pop()
return meeting
def find_meeting_point_map(head1, head2):
ids = {}
ptr1 = head1
while(ptr1!= None):
ids[id(ptr1)] = ptr1
ptr1 = ptr1.next
ptr2 = head2
while(ptr2!= None):
if(ids.setdefault(id(ptr2)) != None):
return ptr2
ptr2 = ptr2.next
print find_meeting_point_map(head1,head2).data