/
linked_list_intersection.py
130 lines (109 loc) · 3.97 KB
/
linked_list_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
#!/usr/bin/python
# Date: 2018-09-20
#
# Description:
# Given 2 linked lists, determine if the two lists intersect. Return the
# intersecting node. Note that the intersection is defined on reference, not
# value.
#
# Approach:
# Check last nodes of both linked lists, if they have same reference, then only
# they can have a intersection point otherwise not.
# Advance longer list by difference in number of nodes in both list. Now
# iterate over both lists and keep comparing references of nodes from both
# lists.
#
# Complexity:
# O(m + n), m and n are lengths of 2 linked lists.
class Node:
def __init__(self, data):
self.data = data # Contains data
self.next = None # Contains reference to the next node
class LinkedList:
def __init__(self):
self.head = None
def add_node_at_start(self, data):
new_node = Node(data) # Create a new node
new_node.next = self.head # Link the new node to the 'previous' node.
self.head = new_node # Set the current node to the new one.
def add_node_at_end(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
return None
node = self.head
while node.next:
node = node.next
node.next = new_node
def list_print(self):
node = self.head
while node:
print('(data: %d id: %d)->' % (node.data, id(node))),
node = node.next
print('None')
def length(self):
node = self.head
count = 0
while node:
count += 1
node = node.next
return count
def get_tail(self):
node = self.head
while node.next:
node = node.next
return node
def linked_list_intersecting_node(self, other_list):
# If both linked list has common last node only then these 2 linked list
# can be intersecting otherwise that's not possible.
if not (self.get_tail() is other_list.get_tail()):
return None
self_len = self.length()
other_len = other_list.length()
if self.length() > other_list.length():
longer_list = self.head
shorter_list = other_list.head
diff_count = self_len - other_len
else:
longer_list = other_list.head
shorter_list = self.head
diff_count = other_len - self_len
# Move longer list ahead by difference between 2 linked list nodes.
count = diff_count
while count:
longer_list = longer_list.next
count -= 1
# Now both linked list has same length from current position to tail
# node. So can just iterate over both linked list and compare their
# references.
# This can also be 'while longer_list:' as both have same length now.
while shorter_list:
if shorter_list is longer_list:
return shorter_list
shorter_list = shorter_list.next
longer_list = longer_list.next
# Driver
linked_list_1 = LinkedList()
linked_list_1.head = Node(1)
linked_list_1.head.next = Node(2)
linked_list_1.head.next.next = Node(3)
linked_list_1.head.next.next.next = Node(4)
linked_list_1.head.next.next.next.next = Node(5)
linked_list_1.list_print()
linked_list_2 = LinkedList()
linked_list_2.head = Node(10)
linked_list_2.head.next = Node(20)
linked_list_2.head.next.next = linked_list_1.head.next.next
linked_list_2.list_print()
common = linked_list_1.linked_list_intersecting_node(linked_list_2)
if common:
print('\nIntersecting node is: (data: %d, id: %d)' % (
common.data, id(common)))
else:
print('\nBoth linked list not intersecting each other')
# Output:
# ----------------------
# (data: 1 id: 140700106383800)-> (data: 2 id: 140700106383872)-> (data: 3 id: 140700106383944)-> (data: 4 id: 140700106384016)-> (data: 5 id: 140700106384088)-> None
# (data: 10 id: 140700106384232)-> (data: 20 id: 140700106384304)-> (data: 3 id: 140700106383944)-> (data: 4 id: 140700106384016)-> (data: 5 id: 140700106384088)-> None
#
# Intersecting node is: (data: 3, id: 140700106383944)