This post is completed by 1 user

  • 0
 Add to List
Medium

21. Linked List cycle detection - Tortoise and Hare Algorithm

Objective: In a given linked list, check whether it contains the loop in it, if yes then find the Loop length and break the loop.

Loop in a linked list means the last node does not point to the null, instead it points to some node in the list.

Input: A Linked List
Output: Linked list contains loop or not, if yes its length and linked list after breaking the loop.

Example: 

Input : -10-20-30-40-50-60-30-40-50-60-30-40-50-60-30

here you can see that 30-40-50-60 are repeating ,that means it has a loop
Loop in a Linked List

Approach:

  • Find the Loop
    • Take two pointers, both starts from head
    • Move one pointer with normal speed and another with double speed (tortoise and hare)
    • If both pointers meets at some point, we have found the loop
  • find the loop length
    • At the point where both pointers have met, stop one pointer and keep moving the another one
    • When another pointer meets the first pointer, stop.
    • Keep counting number of hops, that will the loop length
  • break the loop
    • Move one pointer by the loop length
    • Now move both pointers with normal speed.
    • When secondpointer.next = first pointer, set secondpinter.next=null.

Output:

  -10-20-30-40-50-30-40-50-30-40-50-30-40-50-30

  Loop length is 2
  Loop started at 50
  Loop breaks

  -10-20-30-40-50

Related Problems: