Find the Loop in a Linked list, find its length and Break the Loop

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

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
  • If both pointers meets at some point, we have found the loop
  • Now 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 your loop length
  • Now To 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.

Complete Code:



Output:

->10->20->30->40->50->60->30->40->50->60->30->40->50->60->30
Loop Found--starts at 30
Loop length is 4
Loop breaks

->10->20->30->40->50->60

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

  • dheeraj singhal

    Answer is wrong..how did you assume that when first and second pointer meets that will be start of the loop?

    • tutorialhorizon

      We never assumed that where the both pointers are meeting will be the start off the loop. Then by moving only one pointer and other one stop we will get the length. Now take first pointer (starting from the head) move by the loop length and then move both the pointers, now when the pointers will meet , that will be the starting point of the loop.

      • dheeraj singhal

        Solution description mentioned is correct but code is wrong. Just add one more node at the end after 60 and run your code..u will understand what I m trying to say.

%d bloggers like this: