{"id":4797,"date":"2023-07-18T11:11:12","date_gmt":"2023-07-18T05:41:12","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=4797"},"modified":"2023-07-18T11:21:51","modified_gmt":"2023-07-18T05:51:51","slug":"remove-loop-in-linked-list","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/remove-loop-in-linked-list\/","title":{"rendered":"Remove Loop in Linked List"},"content":{"rendered":"\n<div class=\"gutentoc tocactive nostyle\"><div class=\"gutentoc-toc-wrap\"><div class=\"gutentoc-toc-title-wrap\"><div class=\"gutentoc-toc-title\">Table Of Contents<\/div><div id=\"open\" class=\"text_open\">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=\"#approach-using-hashset\">Approach: Using HashSet<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#algorithm\">Algorithm<\/a><\/li><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=\"#efficient-approach-using-floyd\u2019s-cycle-detection-algorithm\">Efficient Approach: Using Floyd\u2019s Cycle Detection Algorithm<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#algorithm\">Algorithm<\/a><\/li><li><a href=\"#c-code\">C++ Code<\/a><\/li><li><a href=\"#java-code\">Java Code<\/a><\/li><li><a href=\"#python-code\">Python Code<\/a><\/li><\/ul><li><a href=\"#faqs\">FAQs<\/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><\/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. If the linked list contains a loop, return True and remove the loop.<br>A linked list contains a cycle if it consists of a node that can be reached again by continuously following the next pointer.<\/p>\n\n\n\n<p><strong>Examples:<\/strong><br><strong>Input:<\/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><strong>Output: <\/strong>1 -&gt; 2 -&gt; 3 -&gt; 4 -&gt; 5<br><strong>Explanation:<\/strong> The linked list consists of a loop, where the last node connects to the second node. Hence, remove the loop<\/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>1 -&gt; 2<\/p>\n\n\n\n<h2 id=\"approach-using-hashset\">Approach: Using HashSet<\/h2>\n\n\n\n<p>The most straightforward 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. If a node has already occurred before, simply set the current pointer to <strong>NULL<\/strong>.<\/p>\n\n\n\n<h3 id=\"algorithm\"><span id=\"algorithm-2\">Algorithm<\/span><\/h3>\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 hashmap, it ensures that the linked list contains a loop. Hence, set the node to <strong>NULL<\/strong>.<\/li><li>Else, continue traversing and continue inserting the node into the HashSet.<\/li><\/ul><\/li><li>If no node satisfies the above conditions, then the linked list does not contain any cycle.<\/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=\"\">void hashAndRemove(Node * head) {\n  unordered_map &lt; Node * , int > node_map;\n  Node * last = NULL;\n  while (head != NULL) {\n    if (node_map.find(head) == node_map.end()) {\n      node_map[head]++;\n      last = head;\n      head = head -> next;\n    } else {\n      last -> next = NULL;\n      break;\n    }\n  }\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=\"\"> static boolean removeLoop(Node h)\n    {\n        HashSet&lt;Node> s = new HashSet&lt;Node>();\n        Node prev = null;\n        while (h != null) {\n            if (s.contains(h)) {\n                prev.next = null;\n                return true;\n            }\n            else {\n                s.add(h);\n                prev = h;\n                h = h.next;\n            }\n        }\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 removeLoop(head):\n        mp = set()\n        prev = NULL\n        while head is not None:\n            if head in mp:\n                prev.next = NULL\n                return True\n            else:\n                mp.add(head)\n                prev = head\n                head = head.next\n        return False<\/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(N), as HashSet is used<\/li><\/ul>\n\n\n\n<h2 id=\"efficient-approach-using-floyd\u2019s-cycle-detection-algorithm\"><span id=\"efficient-approach-using-floyds-cycle-detection-algorithm\">Efficient Approach: Using 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<h3 id=\"algorithm\">Algorithm<\/h3>\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, the linked list doesn\u2019t contain any cycle. Hence, return False.<\/li><li>Otherwise, move the slow pointer by one node i.e. slow = slow -> next and the <strong>fast <\/strong>pointer by two nodes i.e. <strong>fast = fast -> next -> next<\/strong>.<\/li><li>At any point, if the <strong>fast <\/strong>and the <strong>slow <\/strong>pointers point to the same node, set <strong>node-> next = NULL<\/strong> and return <strong>True <\/strong>as a loop has been detected.<\/li><\/ul>\n\n\n\n<h3 id=\"c-code\">C++ Code<\/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=\"\">void removeCycle(Node * slow, Node * head) {\n  for (Node * curr = head; curr != nullptr; curr = curr -> next) {\n    Node * ptr = slow;\n    while (ptr -> next != slow &amp;&amp; ptr -> next != curr) {\n      ptr = ptr -> next;\n    }\n    if (ptr -> next == curr) {\n      ptr -> next = nullptr;\n      return;\n    }\n  }\n}\nNode * identifyCycle(Node * head) {\n  Node * slow = head, * fast = head;\n \n  while (fast &amp;&amp; fast -> next) {\n    slow = slow -> next;\n    fast = fast -> next -> next;\n    if (slow == fast) {\n      return slow;\n    }\n  }\n  return nullptr;\n}<\/pre>\n\n\n\n<h3 id=\"java-code\">Java Code<\/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 static void removeCycle(Node slow, Node head) {\n  for (Node curr = head; curr != null; curr = curr.next) {\n    Node ptr = slow;\n    while (ptr.next != slow &amp;&amp; ptr.next != curr) {\n      ptr = ptr.next;\n    }\n    if (ptr.next == curr) {\n      ptr.next = null;\n      return;\n    }\n  }\n}\npublic static Node identifyCycle(Node head) {\n  Node slow = head, fast = head;\n \n  while (fast != null &amp;&amp; fast.next != null) {\n    slow = slow.next;\n    fast = fast.next.next;\n    if (slow == fast) {\n      return slow;\n    }\n  }\n  return null;\n}<\/pre>\n\n\n\n<h3 id=\"python-code\">Python Code<\/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 removeCycle(slow, head):\n    curr = head\n    while curr:\n        ptr = slow\n        while ptr.next is not slow and ptr.next is not curr:\n            ptr = ptr.next\n \n        if ptr.next == curr:\n            ptr.next = None\n            return\n \n        curr = curr.next\n \n \ndef identifyCycle(head):\n    slow = fast = head\n \n    while fast and fast.next:\n        slow = slow.next\n        fast = fast.next.next\n        if slow == fast:\n            return slow\n \n    return None<\/pre>\n\n\n\n<ul><li><strong>Time Complexity: <\/strong>O(N), where N is the number of nodes of the linked list.<\/li><li><strong>Space Complexity:<\/strong> O(1), as a map is used.<\/li><\/ul>\n\n\n\n<h2 id=\"faqs\">FAQs<\/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. Read more <a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/blog\/detect-loop-in-linked-list\/\" target=\"_blank\">here<\/a><\/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","protected":false},"excerpt":{"rendered":"Problem Statement Given a linked list. If the linked list contains a loop, return True and remove the&hellip;\n","protected":false},"author":5,"featured_media":4881,"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":[652],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/4797"}],"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=4797"}],"version-history":[{"count":6,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/4797\/revisions"}],"predecessor-version":[{"id":21557,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/4797\/revisions\/21557"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/4881"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=4797"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=4797"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=4797"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}