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.

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

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.