Skip to main content

Find first node of loop in a linked list in python

Python program for Find first node of loop in a linked list. Here problem description and explanation.

#  Python 3 program for
#  Find first node of loop in a linked list

#  Node of Linked List
class LinkNode :
	def __init__(self, data) :
		#  Set node value
		self.data = data
		self.next = None
	

class SingleLL :
	def __init__(self) :
		self.head = None
		self.tail = None
		self.result = None
	
	#  Add new node at the end of linked list
	def insert(self, value) :
		#  Create a new node
		node = LinkNode(value)
		if (self.head == None) :
			self.head = node
		else :
			self.tail.next = node
		
		self.tail = node
	
	#  Display linked list element
	def display(self) :
		if (self.head == None) :
			return
		
		temp = self.head
		#  iterating linked list elements
		while (temp != None) :
			print(temp.data , end = " → ")
			#  Visit to next node
			temp = temp.next
		
		print("null")
	
	#  Find first loop node in given linked list
	def findLoopNode(self, node) :
		if (node == None or node.next == None) :
			#  When get node in loop
			self.result = node
			return node
		
		#  Get next node
		nextNode = node.next
		#  important to control recursion
		node.next = None
		node.next = self.findLoopNode(nextNode)
		return node
	
	#  This method are handles the request the finding loop node
	def firstLoopNode(self) :
		if (self.tail == None or self.tail.next == None) :
			print("Loop not exist")
		else :
			self.result = None
			self.findLoopNode(self.head)
			print("First Loop Node Is : ", self.result.data)
		
	

def main() :
	sll = SingleLL()
	#  Add linked list node
	sll.insert(1)
	sll.insert(2)
	sll.insert(3)
	sll.insert(4)
	sll.insert(5)
	sll.insert(6)
	sll.insert(7)
	print("Linked List")
	#  1 → 2 → 3 → 4 → 5 → 6 → 7 → null
	#  Assume that initial have no loop
	sll.display()
	#  Test Case 1
	#  When no loop
	sll.firstLoopNode()
	#  Test Case 2
	#  When loop exists
	#  Create a new loop
	sll.tail.next = sll.head.next.next
	sll.firstLoopNode()
	#  Create a new loop
	sll.tail.next = sll.head.next.next.next.next
	sll.firstLoopNode()
	#  remove loop
	sll.tail.next = None

if __name__ == "__main__": main()

Output

Linked List
1 → 2 → 3 → 4 → 5 → 6 → 7 → null
Loop not exist
First Loop Node Is :  3
First Loop Node Is :  5




Comment

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