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

[@takeUforward]

Understooooooooooooooood? . Instagram(connect to know closely about updates): instagram.com/striver_79/ . . If you appreciate the channel's work, you can join the family: bit.ly/joinFamily

[@learnwithme7750]

if there is a cycle in it , then it always include last node?

[@yatinarora1252]

@@learnwithme7750hey it depends upon consider if only 1 number and then it may have a cycle also if therre given 1,2,3,4,5 in this case it is said that 2to 3 node value has cycle it is not last node.Use more and more test cases.

[@ankushrai3155]

These videos are so helpful. I have been trying to learn this stuff for a year now. and your videos just click with me. Keep doing the good work sir.

[@infinityzero2321]

Node* fast = head; Node* slow = head; while (fast != slow) { if (fast == NULL || fast->next == NULL || fast->next->next == NULL || slow->next == NULL) return false; fast = fast->next->next; slow = slow->next; } return true; why does this algo not work? tried asking chatgpt but in vain added the fast->next->next and slow_.next to check if that is the issue nut no... i dont understand why is it failing

[@infinityzero2321]

got the mistake 🤣🤣 as soon as i commented realised that I should use do while

[@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)

[@mukundnayak7310]

Thank you!

[@yashlakade179]

Thanks a lot for these.......!!!

[@altafmazhar7762]

Thanks buddy its helpful

[@swapnilparashare2670]

Thank You for clear and simple explanation.

[@pranav288]

what do yall get by copying from leetcode

[@priyankagorkhe2870]

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

[@jaswanthkosanam9481]

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

[@siddharth.chandani]

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

[@ajeetworking]

This series is helping a lot...thanks man

[@aishwarya1895]

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

[@takeUforward]

Thanks for commenting in every video and watching.

[@sriramkrishnamurthy4473]

Bhai vaeya kya hota hai yar ?

[@rajkamalingle9144]

@@sriramkrishnamurthy4473 bhaiya bolna chahti thi shayad

[@om_1_2]

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

[@shashankojha3452]

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

[@takeUforward]

Its in the sde sheet so expect it to be out soon

[@rahulgovindkumar3105]

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

[@ranasauravsingh]

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

[@kaichang8186]

understood, thanks for the great explanation

[@anuragtiwari2098]

The two pointer algorithm is called FLYOD'S LOOP DETECTION . Wud be great if u wud upload the detect and REMOVE loop part too

[@takeUforward]

Coming soon

[@bloke3253]

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

[@takeUforward]

Coming soon

[@farziidentification8672]

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)

[@deepesh16b]

Very good approach 🔥🔥🙏

[@savalalingeshreddy6750]

Thanks for the video bro good explanation Keep doing!

[@samyak1409]

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.

[@GurankitSinghBehal]

You just cleared a massive doubt bro

[@samyak1409]

@@GurankitSinghBehal Hey bro, I just got your reply and read my comment, I was wrong, `head.next == null` IMPLIES that next of head is not pointing to anything. So, returning False is correct. - Samyak with improved DSA. PS: I wonder if I was drunk when I wrote the previous comment. 🤦

[@GurankitSinghBehal]

@@samyak1409 You actually wanted to write...... "fast.next==null"..... I understood it....... And now my question is solved

[@samyak1409]

@@GurankitSinghBehal oh okay!

[@GurankitSinghBehal]

@@samyak1409 yes..... This logic was quite new to me "A single node can point to itself"..... And it can be called a loop in linked list

[@prateekshourya]

Please don't join unacademy 🙏

[@abhimanyu6534]

Great explanation always 💯💯💥🙏

[@SANCHITJAIN_]

great explanation bhaiya..loved it :)

[@dreamyme543]

Great explanation as always. Thank you:)

[@nileshsinha7869]

Awesome👍.. please make day 6 question no. 3 video next 🙏

[@takeUforward]

Coming soon

[@rohitudasi1537]

can we apply recursion and change the value temporary before dfs call and while in dfs if we found temporary value of any node we return true indicating the cycle and after coming from dfs call we again change the value of node to its original value .

[@rohitudasi1537]

//global variable static Node dummy = new Node(-100); public static boolean dfs(Node node){ //if node reached to null we will return false indicating that there is no loop if(node==null){ return false; } // if node reached to the dummy node this means there is a loop if(node == dummy){ return true; } //other wise store node's next in next variable Node next = node.next; //and point node's next to dummy node node.next = dummy; // store the ans in variable but return it after restructuring the link boolean ans = dfs(next); //restructuring the link to original next node.next = next; return ans; }

[@prathamsagar5353]

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

[@sowdub9445]

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

[@ganavin3423]

why can't we use only fast.next.next !=null instead of two condition in while loop

[@atharvakulkarni2024]

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 FINE????? TIME -> O(N) , Space-O(1)

[@abusalin1933]

not O(1) space complexity I think bro if u track numbers from new space where u stored the numbers

[@narsimhareddy4742]

It works check the below code bool hasCycle(ListNode *head) { int changeNum = 1e6; ListNode *temp = head; while(temp!=NULL){ if(temp->val == 1e6){ return true; } else{ temp->val = 1e6; } temp = temp->next; } return false; }

[@loserfruit9663]

Loved the intuition

[@RahulKumar-ed1bt]

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

[@ajay.sinhmar]

We can just directly change the value of every visited node to anything like 10^7 (as every node value in question must be between |10^5| ) and if we found that value again, there's a loop. Do these kind of solution give a bad impression in interview??

[@takeUforward]

Yes, altering of given list is a bad habit, don’t do that. Think in terms pf company work, will u alter a real time data any day like this to find out ans? Try to rekate

[@lakshmiprasanna7058]

Understood 💯💯💯

[@aseemsharma4643]

Why do we increment fast pointer with 2 steps, if we increment it by 3 or 4 step we will reach the cycle faster right? Why 2 step only then?

[@ashwanisingh4931]

Awesome explanation 👌

[@apollodavis4090]

this only works since f1 after the first iteration is one step behind s1 (because of the cycle) thats why it works only when f1 is 2 steps faster not 3 or 4

[@MitrankShah]

Hey Striver, I have a doubt here. We are starting with s = s + 1 and f = f + 2 so initially 'f' is ahead when compared to 's' so why can't we put a condition that when 'f' is behind 's', a cycle would be existing, and we would then return true. Possible?

[@ganavin3423]

I also have the same doubt

[@Rohitkumar-me1uc]

but how in linked list will you decide f is behind s? i think for this you have to do what striver is doing

[@mriduljain1981]

bro you can do it, code will run completely fine bool hasCycle(ListNode *head) { if(head == NULL){ return false; } ListNode* slow = head; ListNode* fast = head; while(fast->next != NULL && fast->next->next != NULL){ slow = slow->next; fast = fast->next->next; if(slow >= fast){ return true; } } return false; } check it out

[@fullysimplified7139]

Hats off to you dude

[@thallapakuteja2350]

will it catches if faster moves 3*slower ? is it possible for any faster=n*slower

[@takeUforward]

Noh, it won’t collide then.

[@kamranahmad8317]

say the loop doesn't start from the end like it start from somewhere in the middle then this 2 pointer approach will fail? wouldn't it?

[@satyamrai445]

where can i get this sde problems sheet ??

[@aryansinha1818]

2:52 to 4:13 advertisement

[@giraffe4375]

Thanks a lot striver

[@harshgupta1913]

Understood. Please Rabin Karp and KMP lago

[@poornimapatel3119]

Bhaiya please answer 🙏, Tier 3 clg with EC can I get placement.

[@poornimapatel3119]

Bhaiya please

[@savalalingeshreddy6750]

@@poornimapatel3119 I am also from EC tier 3 college

[@yashodeepdhas8408]

@@poornimapatel3119 bro u can ofc

[@theparagbagga]

THankyou so much

[@democratcobra]

U r my Hero...

[@rahul.parihar]

Node * fast = head; Node * slow = head; while(fast && fast->next){ fast = fast->next->next; slow = slow->next; if(slow == fast)return true; } return false; Easier && shorter code

[@samayrathod7668]

why their is && in while loop it should be || ?

[@UnKnown-id7ih]

Bhiya it will good for me, if you cover this placement series topic wise. By the way love you bhiya.

[@takeUforward]

Isn’t it getting covered topicwise

[@shreyasingh1258]

Bhaiya please make a video on starting of loop also !🙏

[@takeUforward]

Will come soon

[@shreyasingh1258]

@@takeUforward you the bestt💯💯

[@satyamgupta6030]

thanks striver

[@AyushKumar-ju9jj]

Follow Up Question: WHY can we not use slow inside while loop instead of fast?? Anyone?

[@SDE-wq4tl]

First Approach will fail if list contains duplicate node🤔

[@bsaikumarreddy1413]

Nope bro.. We have to push entire node rather than pushing node value into hash table.

[@krishnasai3367]

@@bsaikumarreddy1413 so what?

[@shamshersinghrawat9377]

@@bsaikumarreddy1413 can you please share the code of 1st approach

[@shawshak2148]

Understood

[@shashankgsharma0901]

Understood!

[@rishabhagrahari3770]

Tier 3 college ke non CS branch se tech companies me placements ( off-campus) ho skta h ? Plz bhaiya log help karo 🙏🙏

[@aryankumar3018]

understood

[@noonetalkseither4315]

am the only one who gets the snoring voice at the back ground ? 🤣🤣🤣🤣🤣🤣🤣🤣🤣🤣🤣🤣🤣🤣🤣🤣🤣

[@devjain1691]

Understooooooooooooooooooooooooooooooooooooooooooooooood

[@ashwinvarma9349]

If cp is generally done with c++ then why teach java?

[@takeUforward]

Just in case..

[@ambermittal8174]

Bhaiya maths weak h kya me competitive coding karlu ga

[@Amritanjali]

yes

[@aashishprateek5030]

could we also use another approach wherein we ask the interviewer the max number of nodes in the linked list, and then what we do is, we keep a count variable initialised to 0, and then run a while loop until the count variable doesn't exceed the maximum number of nodes in the linked list, and keep on incrementing the header to the next node, and if at any point the header reaches NULL, then there is no cycle, otherwise a cycle will exist if the while loop is completed and NULL is not found. it uses O(N) time complexity and O(1) space complexity as you are only using count variable. the code for it is as follows: bool hasCycle(ListNode *head) { int count=0; while(countnext; count++; } return true; }

[@nikhil_squats]

But how to detect where cycle starts??

[@takeUforward]

I have another video on that.. check it out..

[@judgebot7353]

unique algo

[@lokeshvikram6192]

Thx bro

[@ujjwaljain9780]

sir im using this condition in while and all code is same but solution in not accepted ... ... while(fast.next!=null){ .... ...... } please till me why it is not working

[@kunal_chand]

Where is the 2nd & 3rd problem Explanation ?

[@takeUforward]

I explained them but forgot to turn on the screen recording 🤣 realised now when I was searching for the recording to edit. So pushed this to second and moved the other two to bottom. Will come up next day 🙂

[@spongycode]

@@takeUforward 😁

[@letsexplore7590]

😅😅

[@md.imrankhan6912]

magician

[@aasthajain4210]

✨💫

[@surajbugade]

Us