{"id":2905,"date":"2023-07-31T17:59:44","date_gmt":"2023-07-31T12:29:44","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=2905"},"modified":"2023-07-31T18:03:02","modified_gmt":"2023-07-31T12:33:02","slug":"detect-loop-in-linked-list","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/detect-loop-in-linked-list\/","title":{"rendered":"Detect Loop in Linked List"},"content":{"rendered":"\n<div class=\"gutentoc tocactive ullist\" style=\"max-width:400px\"><div class=\"gutentoc-toc-wrap\"><div class=\"gutentoc-toc-title-wrap\"><div class=\"gutentoc-toc-title\">Table Of Contents<\/div><div id=\"open\" class=\"toggletwo\">show<\/div><\/div><div id=\"toclist\"><div class=\"gutentoc-toc__list-wrap\"><ul class=\"gutentoc-toc__list\"><li><a href=\"#problem-statement\">Problem Statement<\/a><\/li><li><a href=\"#hashset-approach\">HashSet Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-implementation\">C++ Implementation<\/a><\/li><li><a href=\"#java-implementation\">Java Implementation<\/a><\/li><li><a href=\"#python-implementation\">Python Implementation<\/a><\/li><\/ul><li><a href=\"#floyd\u2019s-cycle-detection-algorithm\">Floyd\u2019s Cycle Detection Algorithm<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code-for-two-pointer-approach\">C++ Code for Two Pointer Approach<\/a><\/li><li><a href=\"#java--code-for-two-pointer-approach-\">Java  Code for Two Pointer Approach <\/a><\/li><li><a href=\"#python-code-for-two-pointer-approach-\">Python Code for Two Pointer Approach <\/a><\/li><\/ul><li><a href=\"#practice-question\">Practice Question<\/a><\/li><li><a href=\"#frequently-asked-questions\">Frequently Asked Questions<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#q1-how-do-you-detect-a-loop-in-a-linked-list\">Q.1: How do you detect a loop in a linked list?<\/a><\/li><li><a href=\"#q2-will-the-fast-and-slow-pointer-always-meet-at-some-point-if-the-list-contains-a-cycle\">Q.2: Will the fast and slow pointer always meet at some point if the list contains a cycle?<\/a><\/li><\/ul><li><a href=\"#additional-resources\">Additional Resources<\/a><\/li><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<h2 id=\"problem-statement\">Problem Statement<\/h2>\n\n\n\n<p>Given a linked list. Determine if the linked list has a cycle in it.<\/p>\n\n\n\n<p>A linked list contains a cycle if it consists of a node that can be reached again by continuously following the <strong>next<\/strong> pointer.<\/p>\n\n\n\n<p><strong>Examples:<\/strong><\/p>\n\n\n\n<p><strong>Input:&nbsp;<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"211\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-3075 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-2-3-1024x211.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-2-3-1024x211.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-2-3-300x62.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-2-3-768x158.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-2-3-380x78.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-2-3-550x113.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-2-3-800x165.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-2-3-1160x239.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-2-3.png 1471w\" ><\/figure>\n\n\n\n<p><br><strong>Output: <\/strong>True<br><strong>Explanation:<\/strong><\/p>\n\n\n\n<p>The linked list consists of a loop, where the last node connects to the second node.<\/p>\n\n\n\n<p><strong>Input:&nbsp;<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image size-full is-resized\"><img  loading=\"lazy\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-3076 pk-lazyload\"  width=\"318\"  height=\"200\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 318px) 100vw, 318px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-1-3.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-1-3.png 481w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-1-3-300x189.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-1-3-380x239.png 380w\" ><\/figure>\n\n\n\n<p><strong>Output:<\/strong> True<\/p>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"hashset-approach\">HashSet Approach<\/h2>\n\n\n\n<p id=\"the-simplest-approach-to-solve-this-problem-is-to-check-whether-a-node-in-the-linked-list-has-been-visited-before-to-perform-this-operation-a-hashmap-can-be-used\">The simplest approach to solve this problem is to check whether a node in the linked list has been visited before. To perform this operation, a hashmap can be used.<\/p>\n\n\n\n<p><strong>Algorithm<\/strong><\/p>\n\n\n\n<ul><li>Initialise a hashmap.<\/li><li>Traverse the linked list till the <strong>head<\/strong> pointer isn\u2019t <strong>NULL:<\/strong><ul><li>If the current node is already present in the hashset, it ensures that the linked list contains a loop. Hence, terminate and return <strong>True<\/strong>.<\/li><li>Else, continue traversing and continue inserting the node into the hashset.<\/li><\/ul><\/li><li>Return <strong>False<\/strong> if it doesn\u2019t satisfy the above conditions.<\/li><\/ul>\n\n\n\n<h3 id=\"c-implementation\">C++ Implementation<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">bool hasCycle(Node* head) {\n        set&lt;Node*> mp;\n        while (head != null) {\n            if (mp.find(head) != mp.end()) {\n                return true;\n            }\n            mp[head]++;\n            head = head->next;\n        }\n        return false;\n    }<\/pre>\n\n\n\n<h3 id=\"java-implementation\">Java Implementation<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\"> public boolean hasCycle(ListNode head) {\n        Set&lt;ListNode> mp = new HashSet&lt;>();\n        while (head != null) {\n            if (mp.contains(head)) {\n                return true;\n            }\n            mp.add(head);\n            head = head.next;\n        }\n        return false;\n    }<\/pre>\n\n\n\n<h3 id=\"python-implementation\">Python Implementation<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def hasCycle(head):\n        mp = set()\n        while head is not None:\n            if head in mp:\n                return True\n            mp.add(head)\n            head = head.next\n        return False<\/pre>\n\n\n\n<p><strong>Time Complexity:<\/strong> O(N) where N is the number of nodes of the linked list<strong>.<\/strong><br><strong>Space Complexity:<\/strong> O(N), as HashSet is used<\/p>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"floyd\u2019s-cycle-detection-algorithm\"><span id=\"floyds-cycle-detection-algorithm\">Floyd\u2019s Cycle Detection Algorithm<\/span><\/h2>\n\n\n\n<p>This approach uses a two-pointer &#8211; a <strong>fast pointer <\/strong>and a <strong>slow pointer<\/strong> to determine if there exists a cycle in the loop. The <strong>slow pointer<\/strong> moves one node ahead at a time, while the <strong>fast pointer <\/strong>moves two nodes ahead at a time.<\/p>\n\n\n\n<p>If a loop exists in the linked list, the <strong>fast <\/strong>and <strong>slow<\/strong> pointers are bound to meet at some point.<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"522\"  height=\"1024\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-3077 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 522px) 100vw, 522px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-4-1-522x1024.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-4-1-522x1024.png 522w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-4-1-153x300.png 153w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-4-1-380x745.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-4-1-550x1078.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-4-1.png 699w\" ><\/figure>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"1138\"  height=\"519\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-4799 pk-lazyload\"  data-pk-sizes=\"auto\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Image-3.gif\" ><\/figure>\n\n\n\n<p><strong>Algorithm:&nbsp;<\/strong><\/p>\n\n\n\n<ul><li>Initialise two pointers, <strong>fast <\/strong>and <strong>slow <\/strong>to the <strong>head<\/strong> of the linked list.<\/li><li>Traverse through the linked list until the <strong>fast<\/strong> pointer doesn\u2019t reach the end of the linked list.<\/li><li>If the <strong>fast<\/strong> pointer reaches the end, it means that the linked list doesn\u2019t contain any cycle. Hence, return <strong>False.<\/strong><\/li><li>Else, move the <strong>slow <\/strong>pointer by one node i.e. <strong>slow = slow -&gt; next<\/strong> and <strong>fast <\/strong>pointer by two nodes i.e. <strong>fast = fast -&gt; next -&gt; next<\/strong>.<\/li><li>At any point, if the <strong>fast <\/strong>and the <strong>slow <\/strong>pointers point to the same node, return <strong>True <\/strong>as a loop has been detected.<\/li><\/ul>\n\n\n\n<h3 id=\"c-code-for-two-pointer-approach\">C++ Code for Two Pointer Approach<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">\/\/ C++ Code\nbool hasCycle(ListNode *head) {\nif (head == NULL)\nreturn false;\nListNode *slow = head;\nListNode* *fast = head;\ndo {\nif (fast == Null || fast->next == NULL) {\nreturn false;\n}\nslow = slow->next;\nfast = fast->next->next;\n} while (slow != fast);\nreturn true;\n}<\/pre>\n\n\n\n<h3 id=\"java--code-for-two-pointer-approach-\"><span id=\"java-code-for-two-pointer-approach\">Java  Code for Two Pointer Approach <\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">\/\/ JAVA Code\npublic boolean hasCycle(ListNode head) {\n        if (head == null) {\n            return false;\n        }\n        ListNode slow = head;\n        ListNode fast = head.next;\n        do {\n            if (fast == null || fast.next == null) {\n                return false;\n            }\n            slow = slow.next;\n            fast = fast.next.next;\n        } while (slow != fast);\n        return true;\n    }<\/pre>\n\n\n\n<h3 id=\"python-code-for-two-pointer-approach-\"><span id=\"python-code-for-two-pointer-approach\">Python Code for Two Pointer Approach <\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">\/\/ PYTHON Code\ndef hasCycle(self, head: ListNode) -> bool:\n        if head is None:\n            return False\n        slow = head\n        fast = head.next\n        while True:\n            if fast is None or fast.next is None:\n                return False\n            slow = slow.next\n            fast = fast.next.next\n            if(slow == fast)\n                return True\n        return True<\/pre>\n\n\n\n<ul><li><strong>Time Complexity:<\/strong> O(N), where N is the number of nodes of the linked list<strong>.<\/strong><\/li><li><strong>Space Complexity:<\/strong> O(1), as a map is used.<\/li><\/ul>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"practice-question\">Practice Question<\/h2>\n\n\n\n<ul><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/problems\/list-cycle\/\" target=\"_blank\">List Cycle<\/a><\/li><\/ul>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"frequently-asked-questions\">Frequently Asked Questions<\/h2>\n\n\n\n<h3 id=\"q1-how-do-you-detect-a-loop-in-a-linked-list\"><span id=\"q-1-how-do-you-detect-a-loop-in-a-linked-list\">Q.1: How do you detect a loop in a linked list?<\/span><\/h3>\n\n\n\n<p><strong>Ans: <\/strong>A loop can be detected efficiently using the fast and slow pointer algorithm, where the fast pointer moves by two nodes and the slow pointer move by one node at a time.<\/p>\n\n\n\n<h3 id=\"q2-will-the-fast-and-slow-pointer-always-meet-at-some-point-if-the-list-contains-a-cycle\"><span id=\"q-2-will-the-fast-and-slow-pointer-always-meet-at-some-point-if-the-list-contains-a-cycle\">Q.2: Will the fast and slow pointer always meet at some point if the list contains a cycle?<\/span><\/h3>\n\n\n\n<p><strong>Ans:<\/strong> Yes, if the linked list contains a cycle, the fast and slow pointer will always meet at some point.<\/p>\n\n\n\n<h2 id=\"additional-resources\">Additional Resources<\/h2>\n\n\n\n<ul><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/blog\/detect-loop-in-linked-list\/\" target=\"_blank\">Detect Loop in Linked List<\/a><\/li><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/blog\/reverse-a-linked-list\/\" target=\"_blank\">Reverse a Linked List<\/a><\/li><li><a href=\"https:\/\/www.interviewbit.com\/blog\/add-two-numbers-represented-by-linked-lists\/\" target=\"_blank\" rel=\"noreferrer noopener\">Add Two Numbers Represented by Linked Lists<\/a><\/li><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/blog\/intersection-of-two-linked-lists\/\" target=\"_blank\">Intersection of Two Linked Lists<\/a><\/li><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/linked-list-interview-questions\/\" target=\"_blank\">Linked List Interview Questions<\/a><\/li><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/linked-list-mcq\/\" target=\"_blank\">Linked List MCQ<\/a><\/li><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/blog\/application-of-linked-list\/\" target=\"_blank\">Application of Linked List<\/a><\/li><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/blog\/types-of-linked-list\/\" target=\"_blank\">Types of Linked List<\/a><\/li><\/ul>\n","protected":false},"excerpt":{"rendered":"Problem Statement Given a linked list. Determine if the linked list has a cycle in it. A linked&hellip;\n","protected":false},"author":5,"featured_media":3084,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_daextam_enable_autolinks":"1","csco_singular_sidebar":"","csco_page_header_type":"","csco_appearance_grid":"","csco_page_load_nextpost":"","csco_post_video_location":[],"csco_post_video_location_hash":"","csco_post_video_url":"","csco_post_video_bg_start_time":0,"csco_post_video_bg_end_time":0},"categories":[145],"tags":[477],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2905"}],"collection":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/comments?post=2905"}],"version-history":[{"count":10,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2905\/revisions"}],"predecessor-version":[{"id":22192,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2905\/revisions\/22192"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/3084"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=2905"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=2905"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=2905"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}