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
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