{"id":27321,"date":"2018-01-20T21:27:12","date_gmt":"2018-01-20T15:57:12","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27321"},"modified":"2018-01-20T21:27:12","modified_gmt":"2018-01-20T15:57:12","slug":"python-algorithm-write-program-function-detect-loop-linked-list","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/python-algorithm-write-program-function-detect-loop-linked-list\/","title":{"rendered":"Python Algorithm &#8211; Write a program function to detect loop in a linked list"},"content":{"rendered":"<p>Given a linked list, check if the the linked list has loop or not. Below diagram shows a linked list with a loop.<\/p>\n<p><img decoding=\"async\" class=\"aligncenter size-full wp-image-27343\" src=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/Linked-List-Loop-1.png\" alt=\"C Algorithm - Write a program function to detect loop in a linked list\" width=\"300\" height=\"150\" \/><\/p>\n<p>Following are different ways of doing this<br \/>\n<strong>Use Hashing:<\/strong><br \/>\nTraverse the list one by one and keep putting the node addresses in a Hash Table. At any point, if NULL is reached then return false and if next of current node points to any of the previously stored nodes in Hash then return true.<\/p>\n[ad type=&#8221;banner&#8221;]\n<p><strong>Mark Visited Nodes:<\/strong><br \/>\nThis solution requires modifications to basic linked list data structure.\u00a0 Have a visited flag with each node.\u00a0 Traverse the linked list and keep marking visited nodes.\u00a0 If you see a visited node again then there is a loop. This solution works in O(n) but requires additional information with each node.<br \/>\nA variation of this solution that doesn\u2019t require modification to basic data structure can be implemented using hash.\u00a0 Just store the addresses of visited nodes in a hash and if you see an address that already exists in hash then there is a loop.<\/p>\n<p><strong>Floyd\u2019s Cycle-Finding Algorithm:<\/strong><br \/>\nThis is the fastest method. Traverse linked list using two pointers.\u00a0 Move one pointer by one and other pointer by two.\u00a0 If these pointers meet at some node then there is a loop.\u00a0 If pointers do not meet then linked list doesn\u2019t have loop.<\/p>\n<p><strong>Python Programming:<\/strong><\/p>\n<div class=\"code-embed-wrapper\"> <div class=\"code-embed-infos\"> <\/div> <pre class=\"language-python code-embed-pre line-numbers\"  data-start=\"1\" data-line-offset=\"0\"><code class=\"language-python code-embed-code\"># Python program to detect loop in the linked list<br\/> <br\/># Node class <br\/>class Node:<br\/> <br\/>    # Constructor to initialize the node object<br\/>    def __init__(self, data):<br\/>        self.data = data<br\/>        self.next = None<br\/> <br\/>class LinkedList:<br\/> <br\/>    # Function to initialize head<br\/>    def __init__(self):<br\/>        self.head = None<br\/> <br\/>    # Function to insert a new node at the beginning<br\/>    def push(self, new_data):<br\/>        new_node = Node(new_data)<br\/>        new_node.next = self.head<br\/>        self.head = new_node<br\/> <br\/>    # Utility function to prit the linked LinkedList<br\/>    def printList(self):<br\/>        temp = self.head<br\/>        while(temp):<br\/>            print temp.data,<br\/>            temp = temp.next<br\/> <br\/> <br\/>    def detectLoop(self):<br\/>        slow_p = self.head<br\/>        fast_p = self.head<br\/>        while(slow_p and fast_p and fast_p.next):<br\/>            slow_p = slow_p.next<br\/>            fast_p = fast_p.next.next<br\/>            if slow_p == fast_p:<br\/>                print &quot;Found Loop&quot;<br\/>                return<br\/> <br\/># Driver program for testing<br\/>llist = LinkedList()<br\/>llist.push(20)<br\/>llist.push(4)<br\/>llist.push(15)<br\/>llist.push(10)<br\/> <br\/># Create a loop for testing<br\/>llist.head.next.next.next.next = llist.head<br\/>llist.detectLoop()<br\/> <br\/># This code is contributed by Nikhil Kumar Singh(nickzuck_007)<\/code><\/pre> <\/div>\n<p><strong>Output:<\/strong><\/p>\n<pre>Found loop<\/pre>\n<p><strong>Time Complexity:<\/strong> O(n)<br \/>\n<strong>Auxiliary Space:<\/strong> O(1)<\/p>\n[ad type=&#8221;banner&#8221;]\n","protected":false},"excerpt":{"rendered":"<p>Python Algorithm &#8211; Write a program function to detect loop in a linked list &#8211; Linked List &#8211; Given a linked list, check if the the linked list has loop<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[79476,4148,79478],"tags":[76548,81431,81427,81429,81428,81430,81432,80598,81434,81433],"class_list":["post-27321","post","type-post","status-publish","format-standard","hentry","category-linked-list","category-python","category-singly-linked-list","tag-cycle-detection-in-linked-list","tag-detect-cycle-in-linked-list-c","tag-detect-loop-in-linked-list-java","tag-find-merge-point-of-two-lists","tag-find-start-of-loop-in-linked-list","tag-floyds-cycle-finding-algorithm","tag-given-a-linked-list-return-the-node-where-the-cycle-begins-if-there-is-no-cycle-return-null","tag-how-to-find-3rd-element-from-end-in-a-linked-list-in-one-pass","tag-linked-list-cycle-ii","tag-remove-loop-in-linked-list"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27321","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=27321"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27321\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27321"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27321"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27321"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}