Detect a Cycle in Linked List | Amazon | Samsung | Microsoft

In case you are thinking to buy courses, please check below:

#dsa #leetcode #placements

[shiva_krishna_das]

Intuition- let's say 2 people are running in a circular track, one person is running slowly and another person is running faster(2 times the speed of first person)

After a certain period of time person 2 again meet or overtake person 1,

In that case we can conclude that the track is circular ( replace running track with our Linked list)

[priyankagorkhe]

Whenever I need a clarity of a code this is the only platform which gives me transaprency in one shot! Keep it up!!

[siddharth.chandani]

Loved when striverr comes to the part of explaing the intuition behind the logic 🥰

[jaswanthkosanam]

Bruh never stop this series ❤️❤️❤️❤️❤️

[farziidentification]

case 1 if there is no cycle

f reach null and loop will break and it will return false

case 2 if there is cycle

obviously f will come behind s
now f is moving at speed 2x and s is moving with speed x in same direction then we can say
with help of relative speed concept f is moving at speed x and s is at rest wrt f
hence f will surely catch s

f= fast
s= slow

(Physics relative velocity concept involved if you dont know about it ignore this explaination)

[ajeetworking]

This series is helping a lot...thanks man

[kaichang]

understood, thanks for the great explanation

[ranasauravsingh]

UNDERSTOOD... !!!
Thanks, striver for the video... :)

[om__]

Thanks bro. Please don't stop this series, please. Please.

[aishwarya]

Thanks a bunch vaeya... Literally u r a ray of hope for children who are not from iits

[anuragtiwari]

The two pointer algorithm is called FLYOD'S LOOP DETECTION .



Wud be great if u wud upload the detect and REMOVE loop part too

[rahulgovindkumar]

Thanks bro. Please don't stop this series, please.

[shashankojha]

Good Explaination✌❤
This problem can be modified a little if we want to find the starting point of the loop.

[prathamsagar]

while (head != nullptr) {
if (head -> val == 1e5 + 1) return true;
else {
head -> val = 1e5 + 1;
head = head -> next;
}
}
return false;
this has better runtime but assuming u are allowed to write the node values

[samyak]

Isn't the edge case condition "if (head.next == null) return false" wrong, because a Linked List can only have one node and still have cycle, that one node pointing to itself.

[sowdub]

why are we using two conditions in the while loop ?? if fast->next==NULL then fast->next->next will also be NULL only

[savalalingeshreddy]

Thanks for the video bro good explanation
Keep doing!

[atharvakulkarni]

I HAVE GOT ONE MORE APPROACH (OPTIMAL APPROACH)->
FIRST OF ALL ASK THE RANGE OF NUMBERS TO THE INTERVEIWER
THEN PICK A NUMBER OTHER THAN THE RANGE SPECIAIFIED
THEN GO ON TRAVERSING THE LIST FROM THE START AND EVERYTIME YOU TRAVERSE THE LIST IN THE
NODE VALUE PART PUT THAT NUMBER
-> AT ANY POINT WHEN YOU ARE TRAVERSING THE LIST YOU FIND THAT NODE->VAL == THAT NO THEN RETURN TRUE
ELSE RETURN FALSE;.
WILL THIS WORK
TIME -> O(N), Space-O(1)

[RahulKumar-edbt]

Can't we use any Collection class here e.g ArrayList ? Why we have to use HashTable ? In List also we can check if Node exists or not within the collection

[bloke]

It would be very helpful if you could upload head of the loop and remove cycle in a linkedlists Btw awesome explanation as always.