Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

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

Objec­tive: In a given linked list, check whether it con­tains 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

Out­put: Linked list con­tains loop or not, if yes its length and linked list after break­ing 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 point­ers, both starts from head
  • Move one pointer with nor­mal speed and another with dou­ble speed
  • If both point­ers meets at some point, we have found the loop
  • Now find the loop length
  • At the point where both point­ers have met, stop one pointer and keep mov­ing the another one
  • When another pointer meets the first pointer, stop.
  • Keep count­ing num­ber of hops, that will your loop length
  • Now To break the loop
  • Move one pointer by the loop length
  • Now move both point­ers with nor­mal speed.
  • When secondpointer.next = first pointer, set secondpinter.next=null.

Com­plete Code:


Out­put:

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

You may also like...