{"id":644,"date":"2025-07-15T12:55:26","date_gmt":"2025-07-15T07:25:26","guid":{"rendered":"https:\/\/codeanddebug.in\/blog\/?p=644"},"modified":"2025-07-15T12:55:28","modified_gmt":"2025-07-15T07:25:28","slug":"find-length-of-loop","status":"publish","type":"post","link":"https:\/\/codeanddebug.in\/blog\/find-length-of-loop\/","title":{"rendered":"Find length of Loop | Complete\u00a0Guide with 2 Different Solutions"},"content":{"rendered":"\n<p>Given the head of a linked list, determine whether the list contains a loop. If a loop is present,&nbsp;<strong>return the number of nodes<\/strong>&nbsp;in the loop, otherwise&nbsp;<strong>return 0<\/strong>.<\/p>\n\n\n\n<p>Here&#8217;s the [<strong><a href=\"https:\/\/www.geeksforgeeks.org\/problems\/find-length-of-loop\/1\" target=\"_blank\" rel=\"noreferrer noopener\"><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-vivid-purple-color\"><span style=\"text-decoration: underline;\">Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n\n<p><strong>Note: &#8216;<\/strong>c<strong>&#8216;&nbsp;<\/strong>is the position of the node which is the next pointer of the last node of the linkedlist. If c is 0, then there is no loop.<\/p>\n\n\n\n<p><strong>Examples:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted\"><strong>Input: <\/strong>head: 1 \u2192 2 \u2192 3 \u2192 4 \u2192 5, c = 2<strong>\nOutput: <\/strong>4<strong>\nExplanation: <\/strong>There exists a loop in the linked list and the length of the loop is 4.<br><img fetchpriority=\"high\" decoding=\"async\" src=\"https:\/\/media.geeksforgeeks.org\/img-practice\/prod\/addEditProblem\/893387\/Web\/Other\/blobid0_1745983361.jpg\" width=\"340\" height=\"182\"><\/pre>\n\n\n\n<pre class=\"wp-block-preformatted\"><strong>Input: <\/strong>head: 25 \u2192 14 \u2192 19 \u2192 33 \u2192 10 \u2192 21 \u2192 39 \u2192 90 \u2192 58 \u2192 45, c = 4\n<strong>Output: <\/strong>7<strong>\nExplanation: <\/strong>The loop is from 33 to 45. So length of loop is 33 \u2192 <em>10 <\/em>\u2192 21 \u2192 39 \u2192 90 \u2192 58 \u2192 <em>45<\/em> = 7.<br>The number 33 is connected to the last node of the linkedlist to form the loop because according to the input the 4<sup>th<\/sup> node from the beginning(1 based indexing) <br>will be connected to the last node in the LinkedList.<br><img decoding=\"async\" src=\"https:\/\/media.geeksforgeeks.org\/img-practice\/prod\/addEditProblem\/893387\/Web\/Other\/blobid0_1745659828.jpg\" width=\"574\" height=\"146\"><\/pre>\n\n\n\n<pre class=\"wp-block-preformatted\"><strong>Input: <\/strong>head: 0 \u2192 1 \u2192 2 \u2192 3, c = 0\n<strong>Output: <\/strong>0<strong>\nExplanation: <\/strong>There is no loop.<br><img decoding=\"async\" src=\"https:\/\/media.geeksforgeeks.org\/img-practice\/prod\/addEditProblem\/893387\/Web\/Other\/blobid1_1745662178.jpg\" width=\"506\" height=\"105\"><\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><br>1 \u2264 no. of nodes \u2264 10<sup>6<br><\/sup>0 \u2264 node.data \u2264 10<sup>6<\/sup><br>0 \u2264 c \u2264 n-1<\/p>\n\n\n<div style=\"max-width: -moz-fit-content; \" class=\"wp-block-ub-table-of-contents-block ub_table-of-contents ub_table-of-contents-collapsed\" id=\"ub_table-of-contents-1446c7b4-fc8e-4a66-a98d-ed8bde48d776\" data-linktodivider=\"false\" data-showtext=\"show\" data-hidetext=\"hide\" data-scrolltype=\"auto\" data-enablesmoothscroll=\"true\" data-initiallyhideonmobile=\"true\" data-initiallyshow=\"false\"><div class=\"ub_table-of-contents-header-container\" style=\"\">\n\t\t\t<div class=\"ub_table-of-contents-header\" style=\"text-align: left; \">\n\t\t\t\t<div class=\"ub_table-of-contents-title\">Contents:<\/div>\n\t\t\t\t<div class=\"ub_table-of-contents-header-toggle\">\n\t\t\t<div class=\"ub_table-of-contents-toggle\" style=\"\">\n\t\t\t\u00a0[<a class=\"ub_table-of-contents-toggle-link\" href=\"#\" style=\"\">show<\/a>]\n\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t<\/div>\n\t\t<\/div><div class=\"ub_table-of-contents-extra-container\" style=\"\">\n\t\t\t<div class=\"ub_table-of-contents-container ub_table-of-contents-1-column ub-hide\">\n\t\t\t\t<ul style=\"\"><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/find-length-of-loop\/#0-solution-1-brute-force-approach-using-dictionary\" style=\"\">Solution 1: Brute Force Approach (Using Dictionary)<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/find-length-of-loop\/#1-intuition\" style=\"\">Intuition<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/find-length-of-loop\/#2-detailed-approach\" style=\"\">Detailed Approach<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/find-length-of-loop\/#3-code\" style=\"\">Code<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/find-length-of-loop\/#4-code-explanation\" style=\"\">Code Explanation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/find-length-of-loop\/#5-dry-run\" style=\"\">Dry Run<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/find-length-of-loop\/#6-time-and-space-complexity\" style=\"\">Time and Space Complexity<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/find-length-of-loop\/#7-simplifying-it\" style=\"\">Simplifying It<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/find-length-of-loop\/#8-solution-2-optimal-approach-floyds-algorithm-loop-counting\" style=\"\">Solution 2: Optimal Approach (Floyd&#8217;s Algorithm + Loop Counting)<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/find-length-of-loop\/#9-intuition\" style=\"\">Intuition<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/find-length-of-loop\/#10-detailed-approach\" style=\"\">Detailed Approach<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/find-length-of-loop\/#11-code\" style=\"\">Code<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/find-length-of-loop\/#12-code-explanation\" style=\"\">Code Explanation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/find-length-of-loop\/#13-dry-run\" style=\"\">Dry Run<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/find-length-of-loop\/#14-time-and-space-complexity\" style=\"\">Time and Space Complexity<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/find-length-of-loop\/#15-simplifying-it\" style=\"\">Simplifying It<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/find-length-of-loop\/#16-summary\" style=\"\">Summary<\/a><\/li><\/ul>\n\t\t\t<\/div>\n\t\t<\/div><\/div>\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"0-solution-1-brute-force-approach-using-dictionary\">Solution 1: Brute Force Approach (Using Dictionary)<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"1-intuition\">Intuition<\/h3>\n\n\n\n<p>Think of this like taking a walk and marking each step with a number. If you ever come back to a place you&#8217;ve been before, you can easily calculate how many steps you took in the loop by subtracting your current step number from the step number when you first visited that place!<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"2-detailed-approach\">Detailed Approach<\/h3>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Create a Position Tracker<\/strong>: Use a dictionary to store each node and the position where we first encountered it<\/li>\n\n\n\n<li><strong>Walk and Record<\/strong>: Move through the list, recording each node&#8217;s position<\/li>\n\n\n\n<li><strong>Check for Revisit<\/strong>: At each node, check if we&#8217;ve seen it before<\/li>\n\n\n\n<li><strong>Calculate Loop Length<\/strong>: If we find a repeated node, subtract its first position from current position<\/li>\n\n\n\n<li><strong>No Loop Found<\/strong>: If we reach the end, return 0<\/li>\n<\/ol>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"3-code\">Code<\/h3>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro padding-bottom-disabled cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(2 * 0.6 * .875rem);line-height:1.25rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"class Solution:\n    def countNodesInLoop(self, head):\n        my_dict = dict()     # Dictionary to store node -&gt; position mapping\n        temp = head          # Current node we're examining\n        travel = 0           # Current position counter\n        \n        while temp is not None:\n            if temp in my_dict:           # Check if we've seen this node before\n                return travel - my_dict[temp]  # Calculate loop length\n            my_dict[temp] = travel        # Record current node's position\n            travel += 1                   # Increment position counter\n            temp = temp.next              # Move to next node\n        \n        return 0                         # No loop found\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #569CD6\">class<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">Solution<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">countNodesInLoop<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">head<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        my_dict = <\/span><span style=\"color: #4EC9B0\">dict<\/span><span style=\"color: #D4D4D4\">()     <\/span><span style=\"color: #6A9955\"># Dictionary to store node -&gt; position mapping<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        temp = head          <\/span><span style=\"color: #6A9955\"># Current node we&#39;re examining<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        travel = <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">           <\/span><span style=\"color: #6A9955\"># Current position counter<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">while<\/span><span style=\"color: #D4D4D4\"> temp <\/span><span style=\"color: #569CD6\">is<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">not<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">None<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> temp <\/span><span style=\"color: #569CD6\">in<\/span><span style=\"color: #D4D4D4\"> my_dict:           <\/span><span style=\"color: #6A9955\"># Check if we&#39;ve seen this node before<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> travel - my_dict[temp]  <\/span><span style=\"color: #6A9955\"># Calculate loop length<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            my_dict[temp] = travel        <\/span><span style=\"color: #6A9955\"># Record current node&#39;s position<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            travel += <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">                   <\/span><span style=\"color: #6A9955\"># Increment position counter<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            temp = temp.next              <\/span><span style=\"color: #6A9955\"># Move to next node<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">                         <\/span><span style=\"color: #6A9955\"># No loop found<\/span><\/span><\/code><\/pre><span style=\"display:flex;align-items:flex-end;padding:10px;width:100%;justify-content:flex-end;background-color:#1E1E1E;color:#c7c7c7;font-size:12px;line-height:1;position:relative\">Python<\/span><\/div>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"4-code-explanation\">Code Explanation<\/h3>\n\n\n\n<p>We use a dictionary to map each node to its position in our traversal. As we walk through the list, we check if the current node already exists in our dictionary. If it does, we&#8217;ve found the start of the loop! The length of the loop is simply the difference between our current position and the position where we first saw this node. If we reach the end of the list without finding any repeated nodes, there&#8217;s no loop.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"5-dry-run\">Dry Run<\/h3>\n\n\n\n<p>Let&#8217;s trace through:&nbsp;<code>1 -&gt; 2 -&gt; 3 -&gt; 4 -&gt; 2<\/code>&nbsp;(4 points back to 2)<\/p>\n\n\n\n<p><strong>Step 1:<\/strong>&nbsp;temp=1, travel=0, my_dict={}, add 1: my_dict={1: 0}<br><strong>Step 2:<\/strong>&nbsp;temp=2, travel=1, my_dict={1: 0}, add 2: my_dict={1: 0, 2: 1}<br><strong>Step 3:<\/strong>&nbsp;temp=3, travel=2, my_dict={1: 0, 2: 1}, add 3: my_dict={1: 0, 2: 1, 3: 2}<br><strong>Step 4:<\/strong>&nbsp;temp=4, travel=3, my_dict={1: 0, 2: 1, 3: 2}, add 4: my_dict={1: 0, 2: 1, 3: 2, 4: 3}<br><strong>Step 5:<\/strong>&nbsp;temp=2, travel=4, my_dict={1: 0, 2: 1, 3: 2, 4: 3}, 2 found!<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Loop length = 4 &#8211; 1 = 3<\/li>\n<\/ul>\n\n\n\n<p><strong>Result:<\/strong>&nbsp;Loop length is 3!<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"6-time-and-space-complexity\">Time and Space Complexity<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Time Complexity:<\/strong>\u00a0O(n) &#8211; We visit each node at most once before detecting the loop<\/li>\n\n\n\n<li><strong>Space Complexity:<\/strong>\u00a0O(n) &#8211; We store all nodes in the dictionary<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"7-simplifying-it\">Simplifying It<\/h3>\n\n\n\n<p>This approach is like keeping a detailed travel log. When you revisit a place, you can easily count how many steps you took in the circular path by looking at your log. Simple but uses extra memory to store all the positions.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"8-solution-2-optimal-approach-floyds-algorithm-loop-counting\">Solution 2: Optimal Approach (Floyd&#8217;s Algorithm + Loop Counting)<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"9-intuition\">Intuition<\/h3>\n\n\n\n<p>This is a two-step process! First, we use the &#8220;tortoise and hare&#8221; technique to detect if there&#8217;s a loop. Once we find the loop, we keep one pointer fixed and move the other pointer around the loop, counting steps until they meet again. It&#8217;s like sending someone around a circular track and counting how many steps they take to complete one full lap!<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"10-detailed-approach\">Detailed Approach<\/h3>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Phase 1 &#8211; Detect Loop<\/strong>: Use two pointers (slow and fast) to detect if a cycle exists<\/li>\n\n\n\n<li><strong>Phase 2 &#8211; Count Loop Length<\/strong>: Once loop is detected, keep one pointer fixed<\/li>\n\n\n\n<li><strong>Count Steps<\/strong>: Move the other pointer around the loop, counting each step<\/li>\n\n\n\n<li><strong>Complete the Circle<\/strong>: When both pointers meet again, we&#8217;ve counted the entire loop<\/li>\n<\/ol>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"11-code\">Code<\/h3>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro padding-bottom-disabled cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(2 * 0.6 * .875rem);line-height:1.25rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"class Solution:\n    def countNodesInLoop(self, head):\n        slow = head          # Slow pointer (tortoise)\n        fast = head          # Fast pointer (hare)\n        \n        # Phase 1: Detect if loop exists\n        while fast and fast.next:\n            slow = slow.next      # Move slow pointer 1 step\n            fast = fast.next.next # Move fast pointer 2 steps\n            \n            if slow == fast:      # Loop detected!\n                # Phase 2: Count loop length\n                slow = slow.next  # Move slow one step ahead\n                count = 1         # Start counting from 1\n                \n                while slow is not fast:  # Count until they meet again\n                    count += 1           # Increment counter\n                    slow = slow.next     # Move slow pointer\n                \n                return count      # Return loop length\n        \n        return 0                 # No loop found\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #569CD6\">class<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">Solution<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">countNodesInLoop<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">head<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        slow = head          <\/span><span style=\"color: #6A9955\"># Slow pointer (tortoise)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        fast = head          <\/span><span style=\"color: #6A9955\"># Fast pointer (hare)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Phase 1: Detect if loop exists<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">while<\/span><span style=\"color: #D4D4D4\"> fast <\/span><span style=\"color: #569CD6\">and<\/span><span style=\"color: #D4D4D4\"> fast.next:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            slow = slow.next      <\/span><span style=\"color: #6A9955\"># Move slow pointer 1 step<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            fast = fast.next.next <\/span><span style=\"color: #6A9955\"># Move fast pointer 2 steps<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> slow == fast:      <\/span><span style=\"color: #6A9955\"># Loop detected!<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #6A9955\"># Phase 2: Count loop length<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                slow = slow.next  <\/span><span style=\"color: #6A9955\"># Move slow one step ahead<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                count = <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">         <\/span><span style=\"color: #6A9955\"># Start counting from 1<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">while<\/span><span style=\"color: #D4D4D4\"> slow <\/span><span style=\"color: #569CD6\">is<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">not<\/span><span style=\"color: #D4D4D4\"> fast:  <\/span><span style=\"color: #6A9955\"># Count until they meet again<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    count += <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">           <\/span><span style=\"color: #6A9955\"># Increment counter<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    slow = slow.next     <\/span><span style=\"color: #6A9955\"># Move slow pointer<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> count      <\/span><span style=\"color: #6A9955\"># Return loop length<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">                 <\/span><span style=\"color: #6A9955\"># No loop found<\/span><\/span><\/code><\/pre><span style=\"display:flex;align-items:flex-end;padding:10px;width:100%;justify-content:flex-end;background-color:#1E1E1E;color:#c7c7c7;font-size:12px;line-height:1;position:relative\">Python<\/span><\/div>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"12-code-explanation\">Code Explanation<\/h3>\n\n\n\n<p>This solution works in two phases. In Phase 1, we use the classic two-pointer technique to detect if a loop exists. When both pointers meet, we know there&#8217;s a loop. In Phase 2, we move one pointer one step ahead and start counting. We keep moving this pointer around the loop until it meets the other pointer again. The count gives us the exact length of the loop.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"13-dry-run\">Dry Run<\/h3>\n\n\n\n<p>Let&#8217;s trace through:&nbsp;<code>1 -&gt; 2 -&gt; 3 -&gt; 4 -&gt; 2<\/code>&nbsp;(4 points back to 2)<\/p>\n\n\n\n<p><strong>Phase 1 &#8211; Loop Detection:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Initial: slow=1, fast=1<\/li>\n\n\n\n<li>Step 1: slow=2, fast=3<\/li>\n\n\n\n<li>Step 2: slow=3, fast=2 (in loop)<\/li>\n\n\n\n<li>Step 3: slow=4, fast=4<\/li>\n\n\n\n<li>Loop detected! slow == fast at node 4<\/li>\n<\/ul>\n\n\n\n<p><strong>Phase 2 &#8211; Count Loop Length:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Move slow one step: slow=2, fast=4, count=1<\/li>\n\n\n\n<li>Step 1: slow=3, fast=4, count=2<\/li>\n\n\n\n<li>Step 2: slow=4, fast=4, slow == fast, return count=2<\/li>\n<\/ul>\n\n\n\n<p>Wait, let me recalculate this more carefully&#8230;<\/p>\n\n\n\n<p>Actually, let me trace this again:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>When slow and fast meet in the loop, let&#8217;s say they meet at some node<\/li>\n\n\n\n<li>We move slow one step ahead and start counting<\/li>\n\n\n\n<li>We keep moving slow until it comes back to the meeting point<\/li>\n\n\n\n<li>The count will be the length of the loop<\/li>\n<\/ul>\n\n\n\n<p><strong>Result:<\/strong>&nbsp;Loop length is 3 (nodes 2, 3, 4)<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"14-time-and-space-complexity\">Time and Space Complexity<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Time Complexity:<\/strong>\u00a0O(n) &#8211; We traverse the list to detect the loop, then traverse the loop once to count<\/li>\n\n\n\n<li><strong>Space Complexity:<\/strong>\u00a0O(1) &#8211; We only use two pointer variables and a counter<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"15-simplifying-it\">Simplifying It<\/h3>\n\n\n\n<p>This is like having two people on a circular track. First, we confirm they&#8217;re on a circular track by having them run at different speeds until they meet. Then, we keep one person fixed and have the other person walk around the track once, counting their steps. When they meet again, we know the track&#8217;s length!<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"16-summary\">Summary<\/h2>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th>Approach<\/th><th>Time<\/th><th>Space<\/th><th>Difficulty<\/th><th>Best For<\/th><\/tr><\/thead><tbody><tr><td>Brute Force (Dictionary)<\/td><td>O(n)<\/td><td>O(n)<\/td><td>Easy<\/td><td>Learning the concept<\/td><\/tr><tr><td>Two Pointers (Floyd&#8217;s)<\/td><td>O(n)<\/td><td>O(1)<\/td><td>Medium<\/td><td>Production code<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>The&nbsp;<strong>two pointers approach<\/strong>&nbsp;is generally preferred because it uses constant space while maintaining the same time efficiency. However, the brute force approach is more intuitive and easier to understand when you&#8217;re first learning about loop detection.<\/p>\n\n\n\n<p>Both solutions effectively solve the problem, but the optimal solution demonstrates the power of Floyd&#8217;s cycle detection algorithm, <\/p>\n\n\n\n<div class=\"wp-block-buttons is-content-justification-center is-layout-flex wp-container-core-buttons-is-layout-16018d1d wp-block-buttons-is-layout-flex\">\n<div class=\"wp-block-button\"><a class=\"wp-block-button__link wp-element-button\" href=\"https:\/\/codeanddebug.in\/course\/zero-to-hero-python-dsa\" target=\"_blank\" rel=\"noreferrer noopener\">Join our Advance DSA COURSE<\/a><\/div>\n<\/div>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><em>For any changes to the article, kindly email at <a href=\"mailto:code@codeanddebug.in\" target=\"_blank\" rel=\"noreferrer noopener\">code@codeanddebug.in<\/a> or contact us at <a href=\"tel:+91-9712928220\" target=\"_blank\" rel=\"noreferrer noopener\">+91-9712928220<\/a>.<\/em>not just for finding cycles, but for measuring them too!<\/p>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Given the head of a linked list, determine whether the list contains a loop. If a loop is present,&nbsp;return the number of nodes&nbsp;in the loop, otherwise&nbsp;return 0. Here&#8217;s the [Problem Link] to begin with. Note: &#8216;c&#8216;&nbsp;is the position of the node which is the next pointer of the last node of the linkedlist. If c<\/p>\n","protected":false},"author":1,"featured_media":645,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3,6],"tags":[19,29],"class_list":{"0":"post-644","1":"post","2":"type-post","3":"status-publish","4":"format-standard","5":"has-post-thumbnail","7":"category-data-structures-and-algorithm","8":"category-intermediate","9":"tag-medium","10":"tag-singly-linked-list"},"featured_image_src":"https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/07\/find-length-of-loop-featured-image.png","author_info":{"display_name":"codeanddebug","author_link":"https:\/\/codeanddebug.in\/blog\/author\/codeanddebug\/"},"_links":{"self":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/644","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/comments?post=644"}],"version-history":[{"count":1,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/644\/revisions"}],"predecessor-version":[{"id":646,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/644\/revisions\/646"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media\/645"}],"wp:attachment":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media?parent=644"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/categories?post=644"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/tags?post=644"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}