Iam_Sandeep

Detect lloop in linked list

Apr 2nd, 2022 (edited)
194
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.48 KB | None | 0 0
  1. class Solution:
  2.     #Function to check if the linked list has a loop.
  3.     def detectLoop(self, head):
  4.         s,f=head,head
  5.         while  f.next and  f.next.next:
  6.             s,f=s.next,f.next.next
  7.             if s==f:return True    
  8.         return False
  9.            
  10. #{
  11. #  Driver Code Starts
  12. #Initial Template for Python 3
  13.  
  14. # Node Class
  15. class Node:
  16.     def __init__(self, data):   # data -> value stored in node
  17.         self.data = data
  18.         self.next = None
  19.  
  20. # Linked List Class
  21. class LinkedList:
  22.     def __init__(self):
  23.         self.head = None
  24.         self.tail = None
  25.    
  26.     # creates a new node with given value and appends it at the end of the linked list
  27.     def insert(self, val):
  28.         if self.head is None:
  29.             self.head = Node(val)
  30.             self.tail = self.head
  31.         else:
  32.             self.tail.next = Node(val)
  33.             self.tail = self.tail.next
  34.    
  35.     #connects last node to node at position pos from begining.
  36.     def loopHere(self,pos):
  37.         if pos==0:
  38.             return
  39.        
  40.         walk = self.head
  41.         for i in range(1,pos):
  42.             walk = walk.next
  43.        
  44.         self.tail.next = walk
  45.  
  46. if __name__ == '__main__':
  47.     for _ in range(int(input())):
  48.         n = int(input())
  49.        
  50.         LL = LinkedList()
  51.         for i in input().split():
  52.             LL.insert(int(i))
  53.        
  54.         LL.loopHere(int(input()))
  55.        
  56.         print(Solution().detectLoop(LL.head))
  57. # } Driver Code Ends
Add Comment
Please, Sign In to add comment