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.
__________________________________________________

You may also like...

%d bloggers like this: