Home Linked List Find cycle in a linked list. (Method 2)

Find cycle in a linked list. (Method 2)

by nikoo28
1 comment

Question: Given a linked list, return the node where the cycle begins. If there is no cycle, return null.



Output: 0

The easier method to find the cycle has been discussed in this post.

This method is based upon the idea of a circular race track. If there is a slow runner and a fast runner, eventually the fast runner will catch up the slow runner from behind. A similar analogy can be applied to a tortoise and a hare and hence the method is also called Tortoise and Hare method or the Floyd-Warshal algorithm.

The method is divided into 2 steps.

STEP 1: Determine if there is a loop.
The first phase/step of this method is to determine if there is actually any loop in the Linked List. If no loop is found, then we need to directly return null.

STEP 2: Find the loop.

  • We initialize 2 pointers. Fast(hare) and slow(tortoise).
  • Advance slow pointer by 1 step. Advance fast pointer by 2 steps.
  • Keep performing the above step in a loop until both the pointers meet.
  • As soon as they meet, start one more pointer from the beginning of the list.
  • Move the slow pointer and the new pointer one step at a time.
  • The place where they meet is the point where the loop starts in the linked list.

To have a better understanding of why this method works, have a look at the following image.

  • Both hare and tortoise start from POINT 1.
  • The hare covers distance ‘F’ enters the loop and starts moving in the loop at POINT 2.
  • The hare runs for a while as he is fast and moves on path ‘a’.
  • The tortoise now enters the loop at POINT 2 after covering ‘F’ and keeps on moving on path ‘a’. While the hare is now on path ‘b’.
  • The tortoise keeps on moving on path ‘a’ and the hare eventually catches up with the tortoise at POINT 3.
  • Start a new pointer from POINT 1 and it runs at the same speed of tortoise.

We know that speed of hare is double the speed of tortoise.
Let us look at a little math now:-

​2 * distance(tortoise)​ ​​​​= distance(hare)​
2 * (F + a) = F + a + b + a​
​2F + 2a = F + 2a + b
​F​ = b​​

Hence POINT 2 is the point where loop starts.

The source-code for the above algorithm is given below.

// Template for a linked list node class ListNode { int value; ListNode next; } public class Solution { private ListNode getIntersect(ListNode head) { ListNode tortoise = head; ListNode hare = head; // A fast pointer will either loop around a cycle and meet the slow // pointer or reach the `null` at the end of a non-cyclic list. while (hare != null && hare.next != null) { tortoise = tortoise.next; hare = hare.next.next; if (tortoise == hare) { return tortoise; } } return null; } public ListNode detectCycle(ListNode head) { if (head == null) { return null; } // If there is a cycle, the fast/slow pointers will intersect at some // node. Otherwise, there is no cycle, so we cannot find an entrance to // a cycle. ListNode intersect = getIntersect(head); if (intersect == null) { return null; } // To find the entrance to the cycle, we have two pointers traverse at // the same speed -- one from the front of the list, and the other from // the point of intersection. ListNode ptr1 = head; ListNode ptr2 = intersect; while (ptr1 != ptr2) { ptr1 = ptr1.next; ptr2 = ptr2.next; } return ptr1; } }

Time Complexity: O(n)
Space Complexity: O(1)

A sample problem can be found here.

1 comment

You may also like

1 comment

Find cycle in a linked list. (Method 1) | Study Algorithms March 5, 2018 - 22:26

[…] – Find cycle in a Linked List (Method 2) […]

Reply

Enclose codes in [code lang="JAVA"] [/code] tags

This site uses Akismet to reduce spam. Learn how your comment data is processed.

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More