Intersection of two sorted linked lists in python

Python program for Intersection of two sorted linked lists. Here more information.

#  Python 3 program for
#  Intersection of two sorted linked lists
class LinkNode :
	def __init__(self, data) :
		self.data = data
		self.next = None
	

class SingleLL :
	def __init__(self) :
		self.head = None
	
	#  Add new node at the end of linked list
	def insert(self, value) :
		#  Create a node
		node = LinkNode(value)
		if (self.head == None) :
			self.head = node
		else :
			temp = self.head
			#  Find last node
			while (temp.next != None) :
				#  Visit to next node
				temp = temp.next
			
			#  Add node at last position
			temp.next = node
		
	
	#  Display all Linked List elements
	def display(self) :
		if (self.head != None) :
			temp = self.head
			while (temp != None) :
				#  Display node value
				print(" ", temp.data, end = " ")
				#  Visit to next node
				temp = temp.next
			
			print()
		else :
			print("Empty Linked list")
		
	
	def intersection(self, other) :
		if (self.head == None or other.head == None) :
			return
		else :
			#  Get first node of the linked lists
			a = self.head
			b = other.head
			while (a != None and b != None) :
				if (a.data == b.data) :
					#  Display node value
					print(" ", a.data, end = " ")
					#  Visites next upcoming node
					a = a.next
					b = b.next
				elif (a.data > b.data) :
					#  Visit to next node of b
					b = b.next
				else :
					#  Visit to next node of a
					a = a.next
				
			
		
	

def main() :
	sll1 = SingleLL()
	sll2 = SingleLL()
	#  Linked list
	#  0 → 1 → 2 → 3 → 7 → 11 → 21 → NULL
	sll1.insert(0)
	sll1.insert(1)
	sll1.insert(2)
	sll1.insert(3)
	sll1.insert(7)
	sll1.insert(11)
	sll1.insert(21)
	#  Add new element 2
	#  1 → 3 → 7 → 11 → 16 → 17 → NULL
	sll2.insert(1)
	sll2.insert(3)
	sll2.insert(7)
	sll2.insert(11)
	sll2.insert(16)
	sll2.insert(17)
	print("Fist List Element :")
	sll1.display()
	print("Second List Element :")
	sll2.display()
	print("Intersection :")
	sll1.intersection(sll2)

if __name__ == "__main__": main()

Output

Fist List Element :
  0   1   2   3   7   11   21
Second List Element :
  1   3   7   11   16   17
Intersection :
  1   3   7   11



Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment







© 2022, kalkicode.com, All rights reserved