This post is completed by 1 user

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

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.

Code:

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