Detect and Remove Loop in a Linked List | GeeksforGeeks
Вставка
- Опубліковано 12 вер 2024
- Find Complete Code at GeeksforGeeks Article: www.geeksforgee...
Practice Problem Online Judge: practice.geeksf...
Soundtrack: Aretes by Kevin MacLeod
Read More: www.geeksforge...
This video is contributed by Ishant Periwal
Please Like, Comment and Share the Video among your friends.
Also, Subscribe if you haven't already! :)
Hi,
this is a great video, but there's just one thing I'd like to point out that might help others:
this solution doesn't seem to deal with the removal of a full cycle correctly.
when I was testing it out myself I created this loop:
[1]->[2]->[3]->[4]->[5]->[6]->[7]->[1]->[2]->...etc.
the cycle was detected and corrected the linked list to this:
[1]
due to the fast and slow nodes both being at the root/head when the cycle was detected;
moving slow back to root/head meant the while loop checked it's condition, ended, and caused fast->next (which would be node "[2]") to get turned into nullptr, making the list just [1] instead of [1]->[2]->[3]->[4]->[5]->[6]->[7].
had to add an extra conditional to see if both fast and slow were on the root node, and loop the fast pointer around until fast->next was equivalent to the root/head node, and then set fast->next to nullptr.
though the solution is simple enough, it would have been nice to have it included :)
Another way to go around this would be to initialize slow and fast to different nodes(1st and 2nd for example) at the beginning. That way the cycle will still be detected but the loop_node will never be head, but now the nodes must be counted(method 2) to break the cycle.
I use this tutorial as background music while studying. Amazing tutorial thanks G4G!
Geeks For Geeks is the best Platform to master Data Structures As they have the best quality and logical questions and very thoughful.Big Thanks!
The person who made this tutorial needs a HatsOff... Thanks GFG for this.
which software was used to do the animation??
Superb animation
powerpoint.
In the second method, we can remove extra for loop, as
node *removeloop1(node *root, node *loop)
{
node *ptr1,*ptr2;
ptr1=loop; / /meeting point of the fast and slow pointer meet.
ptr2=root; //head
while(ptr1->next!=loop){
ptr1=ptr1->next;
ptr2=ptr2->next;
}
ptr1=root;
while(ptr2->next!=ptr1){
ptr2=ptr2->next;
ptr1=ptr1->next;
}
ptr2->next=NULL;
return root;
}
Simply superb, no wasting of time and easy understanding ❤
thanks for your hard work for better understand.
so easy to understand, big thanks!
You're welcome Tran Duc!
nice explaination but i think in detection of loop .......
in while loop statement writing "while fast.next and fast" would be sufficient......correct me if i am wrong
you are wrong
That will work!
great, I had one more approach although it uses extra memory. While traversing, keep pushing the nodes in map. If anytime we get the same node again, we will find out that instance, not only we will be able to detect the loop, but also the node where loop happens.
1-2-3-1 .... last method is not working on this test case , in this slow and fast pointer is coming on head pointer which is "1" while detecting loop , ... can anyone help me out ??
awesome videos best way to learn interview question and best way to learn DS
Simply superb :)
Thanks Soumava Nag :)
Best video so far
In 3rd method we need some modification:
we have to check condition that it is not forming complete cycle(i.e circular linked list).In case of circular linked list fast && slow are pointing to head that's why while loop is not working.
c++ code:
if(slow==fast)
{
slow=head;
if(slow == fast) {
while(fast->next != slow) fast = fast->next;
}
else
{
while(slow->next!=fast->next)
{
slow=slow->next;
fast=fast->next;
}
}
fast->next=NULL;
}
This is linked list, so it will definitely be different from circular linked lists.
best way to teach ds
One of the best video!
Thanks Rahul!
Nicely explained
Thanks Kaushal!
Hi All,
I didn't quite understand the fact that if k+m is a multiple of n then how the fast pointer and the slow pointer will meet at the starting point of the loop? Can Anyone help me understand it?
Let us say that n=k+b.---(1) and it has already been proved that k+m is a multiple of n.
=>(k+m)=a*n---(2)
Subtracting two equations,
=>m-b=(a-1)*n
=>m= b+(a-1)*n
Hence it suggests that m is the distance equal to certain number of full iterations in the circle and distance b. hence, they definitely meet.
(k+m) is multiple of n, so
k+m=a*n where a is that multiple
shifting k to right
m=(a*n) - k
for simplicity let's see (a*n) as 'n' only
m=n-k
This (n-k) is the distance between meeting point(k) and start of the cycle .(refer diagram)
From this point one went to head. So if ptr1 starts from head and covers 'm' distance, then it's bound to meet ptr2 which starts from that meeting point(k) and reaches start point of cycle.
I doubt if method 3 works...I don't understand...what if the head is at 2 or the linked list had another head say 0... wouldn't it make it loop infinitely?
Last method does not work for multiple test cases
nice explanation!
You saved a headache !
In the second method, why is it that ptr2 will only terminate once it can reach ptr1? Why can't we check for ptr2->next == loop_node and make the cut there to cut off the loop? Thanks.
Because the equation works for all size of loop. You don't really know where the start of the loop is at that point. You need to find it. Basically, if it takes K steps for the slow runner to enter the loop, and the fast runner moves at double the pace as the slow runner. Then the fast runner is 2K - K step or K steps into the loop. 1) When the slowRunner is 0 step inside the loop. 2) The fastRunner is K steps into the loop. 3) slowRunner is K steps behind FastRunner. 4) FastRunner is Loop_size - K steps behind slowRunner. So because fastRunner catches up to the slowRunner at a pace of 1 per step. It will take Loop_size - K to catch up to it. so if you have a loop size of 8 and your fastRunner is 3 steps into the loop which = K. And if you traverse the difference (Loop_size-k) of 5 steps to get to where they collide then it means that there are 3 more steps or k steps to the head of the circle. Because K = mod(k, loop_size), this works for any size of loop. And since it took slowRunner k step to get inside of the loop, the collision spot and head of the linked list is K steps away from the beginning of the loop. Then you can move the slow pointer back to the beginning and move step by step to find the head of the loop.
nice info, thanks.
I have a question why traversing at 2 for ptr2 ?
why cant be 3X ?
cannot, the equation doesn't work for 3x.
Can find the loop....but loop removal can't use the formula...
Can anyone help? whats going wrong here?
void removeLoop(Node* head)
{
// code here
// just remove the loop without losing any nodes
Node *slow, *fast;
slow = head;
fast = head;
slow = slow->next;
fast = fast->next->next;
while(fast && fast->next) {
if(slow == fast)
break;
slow = slow->next;
fast = fast->next->next;
}
if(slow == fast) {
slow = head;
while(slow->next != fast->next) {
slow = slow->next;
fast = fast->next;
}
fast->next = NULL;
}
}
input:-
4
1 2 3 4
1
output:-
0 // not removed
expected output:-
1 // removed
how 2nd method is solving problem where there are more nodes than k count before loop.
like. 2->3->4->5->6->7->9->10->11->12->13->14->11 . 4 nodes in loop. so ptr1 and ptr2 both will start from head and after k(4) ptr2 will be at 6. I did not get how ptr1 and ptr2 are always going to meet on loop start node. I mean i din get math here. Might be sue to logic explain in 3rd.
but nice video with superb animation.
I came here looking for better explanation to this solution but didn't find it. Let me try to explain it to you and maybe I will get it in the process as well. If it takes K steps for the slow runner to enter the loop, and the fast runner moves at double the pace as the slow runner. Then the fast runner is 2K - K step or K steps into the loop. 1) When the slowRunner is 0 step inside the loop. 2) The fastRunner is K steps into the loop. 3) slowRunner is K steps behind FastRunner. 4) FastRunner is Loop_size - K steps behind slowRunner. So because fastRunner catches up to the slowRunner at a pace of 1 per step. It will take Loop_size - K to catch up to it. so if you have a loop size of 8 and your fastRunner is 3 steps into the loop which = K. And if you traverse the difference (Loop_size-k) of 5 steps to get to where they collide then it means that there are 3 more steps or k steps to the head of the circle. Because K = mod(k, loop_size), this works for any size of loop. And since it took slowRunner k step to get inside of the loop, the collision spot and head of the linked list is K steps away from the beginning of the loop. Then you can move the slow pointer back to the beginning and move step by step to find the head of the loop. Wow explaining it to someone else really helped me get this. I hope it helped you too. Let me know if something confused you.
In the 2nd method what if there are some 10 or 20 nodes before the head node of the loop(in this case 3th node) with the size of the loop still 6.For eg,the list is 0-10-11-1-2-12-13-14-15-16-17-(3-4-5-6-7-8) where 3 till 8 forms the loop.The ptr2 after the for loop it will be pointing somewhere in the linear part of the list which cannot move in cycle.Plizz explain
ptr2 doesn't need to start inside the loop.
In the last step, ptr1 will start at 0 and ptr2 will start at 13.
Then, you move both of them until they meet. They will both move 11 steps (ptr2 will make one loop) until they meet at 3.
If it takes K steps for the slow runner to enter the loop, and the fast runner moves at double the pace as the slow runner. Then the fast runner is 2K - K step or K steps into the loop. 1) When the slowRunner is 0 step inside the loop. 2) The fastRunner is K steps into the loop. 3) slowRunner is K steps behind FastRunner. 4) FastRunner is Loop_size - K steps behind slowRunner. So because fastRunner catches up to the slowRunner at a pace of 1 per step. It will take Loop_size - K to catch up to it. so if you have a loop size of 8 and your fastRunner is 3 steps into the loop which = K. And if you traverse the difference (Loop_size-k) of 5 steps to get to where they collide then it means that there are 3 more steps or k steps to the head of the circle. Because K = mod(k, loop_size), this works for any size of loop. And since it took slowRunner k step to get inside of the loop, the collision spot and head of the linked list is K steps away from the beginning of the loop. Then you can move the slow pointer back to the beginning and move step by step to find the head of the loop.
Kindly add voice over please
last method fails when i goes to submit code of last approach:
check for circular linked list condition.
c++ code:
if(slow==fast)
{
slow=head;
if(slow == fast) {
while(fast->next != slow) fast = fast->next;
}
else
{
while(slow->next!=fast->next)
{
slow=slow->next;
fast=fast->next;
}
}
fast->next=NULL;
}
@@manikanth.8507 Thanks man, Trying to find a solution since two hours . Your comment came as miracle !!!
superb!! fabulous
loop same with cycle?
Can someone tell me what is the use of finding k ?
anyone the intuition behind the seconnd method ????
Better way of explanation .........
Thankyou..🥰🥰😍😍😍
wow this is amazing
AMAZING !
AWESOME.
Thanks kashish mittal :)
Perspicuously Explained
Nice graphics
Such music.
wow.
Thanks :)
Please share name of music
Bingo !
wth is this backgroung music