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

  • dheeraj sing­hal

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

    • tuto­ri­al­hori­zon

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

      • dheeraj sing­hal

        Solu­tion descrip­tion men­tioned is cor­rect but code is wrong. Just add one more node at the end after 60 and run your code..u will under­stand what I m try­ing to say.