Skip to main content

Find length of loop in linked list in python

Python program for Find length of loop in linked list. Here problem description and explanation.

#  Python 3 Program for 
#  Find length of loop in linked list 
class LinkNode :
	def __init__(self, value) :
		self.data = value
		self.next = None
	

class SingleLL :
	def __init__(self) :
		self.head = None
	
	#  Insert node at last of linke list
	def insert(self, value) :
		#  Create a node
		node = LinkNode(value)
		if (self.head == None) :
			#  First node
			self.head = node
		else :
			temp = self.head
			#  Find lase node
			while (temp.next != None) :
				temp = temp.next
			
			#  Add node
			temp.next = node
		
	
	#  Find the length of loop
	def lengthLoop(self) :
		if (self.head == None) :
			print("Empty Linked List ")
		else :
			#  Case : Check whether if loop
            #         exists in given linked list
			#  Auxiliary variables
			first = self.head
			second = self.head
			counter = 0
			#  Detecting the loop in linked list
			while (second != None and 
                   second.next != None and 
                   second.next.next != None) :
				#  Visit to next node
				first = first.next
				#  Visit to second next node
				second = second.next.next
				if (first == second) :
					#  Loop is found
					counter = 1
					break
				
			
			if (counter == 1) :
				#  Count the length of loop
				while (first.next != second) :
					#  Visit to next node
					first = first.next
					counter += 1
				
			
			print("Length of Loop : ", counter)
		
	

def main() :
	task = SingleLL()
	task.insert(1)
	task.insert(2)
	task.insert(3)
	task.insert(4)
	task.insert(5)
	task.insert(6)
	task.insert(7)
	task.insert(8)
	#  Create Loop
	task.head.next.next.next.next.next.next.next.next = task.head.next.next
	task.lengthLoop()

if __name__ == "__main__": main()

Output

Length of Loop :  6




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