This post is completed by 1 user
|
Add to List |
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
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
Also Read: