Linked List Cycle - Floyd's Tortoise and Hare - Leetcode 141

Linked List Cycle - Floyd's Tortoise and Hare - Leetcode 141 - Python

Рет қаралды 187,364

Күн бұрын

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
⭐ BLIND-75 SPREADSHEET: docs.google.com/spreadsheets/...
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 CODING SOLUTIONS: • Coding Interview Solut...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
🌲 TREE PLAYLIST: • Invert Binary Tree - D...
💡 GRAPH PLAYLIST: • Course Schedule - Grap...
💡 BACKTRACKING PLAYLIST: • Word Search - Backtrac...
💡 LINKED LIST PLAYLIST: • Reverse Linked List - ...
Problem Link: neetcode.io/problems/linked-l...
0:00 - Read the problem
3:34 - Drawing Explanation
9:22 - Coding Explanation
leetcode 141
This question was identified as an amazon interview question from here: github.com/xizhengszhang/Leet...
#linked #list #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

Пікірлер: 189

@NeetCode 3 жыл бұрын

💡 LINKED LIST PLAYLIST: kzfaq.info/get/bejne/fZaPfJCLq5a3Y2w.html

@algorithmo134 3 жыл бұрын

@NeetCode can you solve binary tree cameras a dp question next? TQ

@joelbisponegrao9932 2 жыл бұрын

This guy is insane, he is helping a whole bunch of people getting new jobs and understanding algo than anyone ever. He deserves the best.

@misterimpulsism 2 жыл бұрын

I've seen Floyd's Tortoise & Hare algorithm many times and have taken it for granted. This is by far the best explanation of why it works and why it's O(n) time. Many thanks to Neetcode!

@gayan1742 2 жыл бұрын

Explaining how it always evaluates to O(n) is really helpful.

@juliuscecilia6005 3 жыл бұрын

hands down best leetcode youtuber

@sanjanar9198 2 жыл бұрын

Please keep posting solutions like this, they are really helpful

@ruzaikr 6 ай бұрын

The explanation of the Floyd's Tortoise and Hare algorithm was amazing!

@McBritish 2 жыл бұрын

Always love your videos. I've been working hard on LC problems for the last 10 days and I always come to these videos when I get stuck or would love to learn a clean, concise solution.

@rioredwards Жыл бұрын

Great solution! I found one that is simpler, although might be considered the "easy way out".... If you set each node's value to None/null/undefined (depending on the language), then you can just check for if the current node is undefined in the loop. This solution is slightly faster than the slow/fast pointer method: class Solution(object): def hasCycle(self, head): if not head: return False while head.next: if head.val == None: return True head.val = None head = head.next return False

@Jesseiceheart 9 ай бұрын

Great solution: 1. Altering source linked list is not idael in a real time scenario, unless the arg passed is already a deep copy of the original linked list and not just a shallow copy. 2. If we had to create a deep copy ourselves, it'll add up to the memory utilised by our solution.

@licokr 4 ай бұрын

It's crazy. To undderstand Floyd's Tortoise and Hare, I watched a lot of videos on KZfaq but it couldn't work and I gave up. Today, I was solving Leetcode 141 problem and to find a solution with space O(1), I watched it and wow... There were already lots of times 'WOW' while watching neetcode' videos, but wow... 10-(2-1), n-1.. this guy got me understand this. just with two lines. Crazy. I learn a lot from your videos, not only algorithm...

@stormarrow2120 2 жыл бұрын

to be technical, when you store an object like a Node in a dictionary in python we are storing the address in the dictionary/set. That is how we can be sure that we have not seen it before using the "hashset" approach. Felt it was worth commenting. BTW saw your video the other day about you working in Seattle at Google! well deserved. I love your content! You may look into becoming a CS teacher when you're burnt out working at major tech giants. haha keep them coming!

@osmanmusse9432 2 жыл бұрын

Thanks for telling us

@cadenc.7368 Жыл бұрын

Thank you! I was wondering how the objects were being stored in the hashset since the node objects themselves are not hashable, but now I see that their memory addresses are.

@sujal1548 Жыл бұрын

when you are doing the comparison of fast == slow, what exactly is happening? Are the memory addresses being compared in that way as well? If so, what is the difference between the comparison x == 5 where x is 5 and fast == slow? How does Python know to compare memory addresses for fast and slow and actual values for x == 5?

@sujal1548 Жыл бұрын

chatgpt answer to my question, let me know if it's correct: In Python, the comparison x == 5 is different. It compares the value of the variable x (which is 5) with the value 5. Python knows that x is an integer, so it compares the integer value directly. However, when it comes to objects in Python, such as the ListNode instances in the linked list, the comparison slow == fast compares the memory addresses of the objects. It checks whether slow and fast are referring to the same object in memory, rather than comparing the contents of the objects.

@BudetSvobodnoy 5 ай бұрын

@@sujal1548 good question, I'd love to know how it works in JavaScript as well. Not sure if we should trust gpt on this one

@Andres-dn8ze 2 ай бұрын

@neetcode is goated! I was having a hard time with some of the previous linked list questions in neetcode 150 but with this one I was able to solve it first by using a hashSet and then did the follow up once I saw someone mention tortoise and hare's algo because i assumed it had to mean slow and fast pointers if memory complexity was O(1). I feel like with a lot of the leetcode questions you keep getting beat up until eventually some of the topics 'click' and then you finally start seeing the fruits of your labor! Thanks neetcode you're the man 🙏

@seanmcelroy4074 Жыл бұрын

Thanks, explaining the slow pointer increases the distance by 1 and the fast pointer decreases distance by 2 shows how the distance is always decreasing by 1 so fast will never overtake!

@NeetCode Жыл бұрын

Thank you so much!

@moewiseman1557 Жыл бұрын

unless it overtake by surpassing the slow pointer in this case it might take more than 1 cycle right?

@adewumisunkanmi5593 2 жыл бұрын

Honestly, this is a technique anyone should not miss..it just makes the whole problem easy to solve.Thanks NeetCode

@_ipsissimus_ 2 жыл бұрын

"Given Head" lmao these leetcode prompts are juicy

@yinglll7411 3 жыл бұрын

Thank you man, as soon as you mentioned two pointers it just clicked for me. Thank you!

@TenzDelek 3 ай бұрын

every time brings a whole new concept to learn. grateful for that

@taco564 Жыл бұрын

Amazing explanation on why it's linear time! Thank you!!

@emmanueltemiede6197 Жыл бұрын

best explanation for the Tortoise and hare algorithm i have seen so far, thanks

@wlcheng 2 жыл бұрын

Brilliant solution! Thank you for creating this video!

@bandhammanikanta6302 2 жыл бұрын

Thank you for solving the problem with first brute force and then with the optimised solution.

@osmanmusse9432 2 жыл бұрын

Wow that was great explanation you just did, I really appreciate it neetcode for what your doing I know you work also it can be hard making these sort of videos with great visual solution.

@80kg 2 жыл бұрын

Thank god this is such an amazing explanation!!! AS ALWAYS!!!

@itstheguy17 2 жыл бұрын

Very clear and detailed explanation, thanks a lot!

@sahilkassanjee802 2 жыл бұрын

Great explanation. I wasn't understanding the second method, but you explained it perfectly

@bianchialex 2 жыл бұрын

I didnt understand this algorithm for legit a year until today. Thank you.

@rajeshseptember09 2 жыл бұрын

perfectly articulated explanation. Thanks much ! I could only think of a hashMap solution - but the hare and tortoise pointer approach is much more efficient.

@juliramoos 5 ай бұрын

I loooove the way you explain things. Make them so much easier

@devin3944 8 ай бұрын

Fantastic visualization as to why the 2 offset pointers work

@saurabhkathar2374 2 жыл бұрын

Great Explanation, you are the best teacher for coding solutions🙏🙏

@symbol767 2 жыл бұрын

Thanks man just wanted to see how you coded it out, you the man! Liked

@noobletify869 2 жыл бұрын

An explanation I can actually understand 😅 Thanks!!

@The6thProgrammer 9 ай бұрын

Since there were no rules against modifying the original linked list, my approach was to actually move through the linked list and reverse the list as I traversed it. I only had to store a single node in a hash map (the original head) so the memory complexity was O(1). Once you move through a cycle all the nodes you encounter after the cycle are now reversed so the path will take you back to the original head and you can return true if you find a match against the single node in the hash map, otherwise false if you encounter NULL.

@evgeniyazarov4230 9 ай бұрын

Did the same, yet you don't need a hashmap to store the list's head, just save a pointer to it

@The6thProgrammer 9 ай бұрын

@@evgeniyazarov4230 good point!

@nghiavo6263 Жыл бұрын

You blowed my mind with fast and slow pointer technique

@SiddharthRanjan6197 2 ай бұрын

@NeetCode a more intuitive way to understand this by taking a real world example i.e., an analog clock. The seconds hand moves faster than the rest but because all hands move in a circle...they are bound to converge at certain point in time.

@MacAndSwiss 2 жыл бұрын

Nice video! The proof was super helpful.

@ankitdubey5045 7 күн бұрын

Those who have studied relative motion can easily understand it,taking slow to rest then the fast will meet the slow that is at rest

@pjchen8605 10 ай бұрын

Super helpful and amazing explanation! Thanks so much!

@Relqeds 2 жыл бұрын

Awesome....I like the way you explain ...very clean and easy way...pls keep posting ..thank you!!

@tomonkysinatree 6 күн бұрын

Great explanation, I feel like the coding portion really avoided some odd edge cases and made it seem simpler than it is. For example, we started the pointers at the same point and then updated the pointers first instead of at the end of the loop.

@musicgotmelike9668 Жыл бұрын

Something about your pronounciation just makes me understand the topics;) Keep up the great work!

@pranjalnama2420 Жыл бұрын

amazing explanations sir, did not understand this algo before but you made it pretty easy

@user-dw6zi4yo3i Жыл бұрын

Cystal clear explanation, thanks a lot!

@jackchen5288 2 жыл бұрын

Thanks for all the explanations!

@adarshsasidharan254 Жыл бұрын

hands down the best explanation/proof of the Floyd's Cycle Detection Algorithm

@azatnurzhanuly7290 2 жыл бұрын

That was a great video tutorial about the topic, thank you!!!!

@CodingWithPrakash_ 2 жыл бұрын

Best explanation for why floyd algo works

@pedroalonsoms 7 ай бұрын

excellent explanation on why slow and fast eventually meet each other

@annsway 2 жыл бұрын

Thank you so much! It helped a lot!

@kmeenakshi2679 Жыл бұрын

Next level explanation Dude..!! Just loved it :D

@hemesh5663 2 жыл бұрын

Hands down best youtube channel.

@sriramkrishnamurthy4473 2 жыл бұрын

NOW THAT IS WHAT IS AN INTUITIVE EXPLANATION ❤🙏🙏👍

@binup28 2 жыл бұрын

Great explanation! Thank you. Could you kindly do a similar awesome explanation for leetcode 142 Linked List Cycle II ?

@alpyldrm8448 Жыл бұрын

I have managed to solve it with a hash map but this is a much elegant solution. Thanks for the video.

@vimalalwaysrocks Жыл бұрын

This is not Leetcode, this is "Neet" code. Excellent! Would have loved it if you could have also added how to find the node of the loop start which is what 142. Linked List Cycle II is asking us to find.

@nikakondra5321 10 ай бұрын

Thank you so much for this explanation

@AliHassan-ec9nu 9 ай бұрын

thansk for such an awesome explanation.

@weaammohamed8992 2 жыл бұрын

Amazing explanation thank you!

@alextech4881 Жыл бұрын

Eureka effect on steroids. Thanks so much for posting these, they really help A LOT!

@gradientO Жыл бұрын

Best explanation of why runner catches up with walker!

@shenzheng2116 2 жыл бұрын

Thanks for your helpful explanation ! Could you explain Linked List Cycle II in the next video?

@Bhaskar5890 2 жыл бұрын

Hey....... you have great teaching skills... please create a separate array and string playlist....... also which s/w you use for drawing explanations.

@Aalii6 2 жыл бұрын

very clear, thank you!

@krateskim4169 2 жыл бұрын

simple beautiful,great job

@mohamadilhamramadhan6354 Жыл бұрын

Thanks. Learn something new here.💌

@naimeimran3247 2 жыл бұрын

Nice solution. Thanks a lot

@araibkarim7816 2 жыл бұрын

Great explanation!

@flatmapper 6 ай бұрын

Amazing explanations

@amanhasnoname836 2 жыл бұрын

the explanation is really awesome

@dzianisdashkevich1848 2 жыл бұрын

Amazing, thanks!

@JustinK0 4 ай бұрын

i just used a map to save the nodes address as a string, so if node.next's address is already in the map its a cycle, not as fast as this but its still O(n), just uses more memory

@VivekGawande1 Жыл бұрын

What a great explanation!

@akshaibaruah1720 2 жыл бұрын

i never really comment on ytb videos but this was so well explained that I simply have to commend you for this great explanation!!

@helikopter1231 2 жыл бұрын

If i dont want to use a different class, how can i incorporate the next function and also use the head? Otherwise, amazing explanation!!

@kaydeeinmy 5 ай бұрын

omgg, Neetcode you're the legendary !!!!!

@mehmetnadi8930 2 жыл бұрын

spicy solution! love it!

@furkan486 3 ай бұрын

Clean explanation

@altusszawlowski4209 6 ай бұрын

Great explanation! Although since the problem doesnt state that we are not allowed to manipulate the linked list, we can just change all the vals to None as we see them and check if the val is None to determine a cycle. This obviously wouldnt work if the input had nodes with vals of None though.

@rohithjanardhan4970 2 жыл бұрын

Amazing explanation, tysm

@SteveInTek 2 жыл бұрын

dang! perfect explaination 💯

@swarupsarangi734 2 жыл бұрын

awesome explanation of the algorithm

@SmrutiDashiamironman Жыл бұрын

Thanks for explaining so well.. 😊

@NeetCode Жыл бұрын

Thank you 🙏

@TransparentWorld1275 Жыл бұрын

You mentioned at the beginning of the video that you already completed a problem already similar to this - which video/topic is that? The "Finding a duplicate number" video?

@akermiyu 2 жыл бұрын

Why do we moved the fast pointer by 2 instead of another number? Does moving the slow pointer by 1 and the fast pointer by 2 always ensure that we can catch a cycle if there is one?

@sabba2_ 5 ай бұрын

With the first approach you can simply edit node values to something unique, so if you encounter your unique value again it means you detected a cycle. O(n) time O(1) space.

@adityachache 2 жыл бұрын

I did this and the second version of this where we have to return the node by using hash table

@samrey8134 2 жыл бұрын

..... Your explanation is Crack ... Thank you so much.😀

@algorithmo134 3 жыл бұрын

@NeetCode can you solve binary tree cameras a dp question next?

@juanelias1309 Жыл бұрын

Thank you so much!

@chunkwanchan5503 7 ай бұрын

if fast & slow start at different node, and the fast pointer move 3 or 4 or 5 times faster than the slow pointer. I found that in some cycle structure, the two pointers will never meet, why is that? Thanks in advance.

@samwilson4597 2 жыл бұрын

this man is the GOAT

@wilsonwang8641 2 жыл бұрын

The most valuable part to me starts from 8:20.

@Ahmad_Al-Deeb 3 ай бұрын

Thanks a lot. I would appreciate if you can tell me the tool you are using for drawing.

@ikthedarchowdhury8947 2 жыл бұрын

Can't we use Valid palindrome solution here? Like using Two pointers but in polar opposite nodes/ pointers? Then checking if l = r?

@quanhoangminh2975 2 жыл бұрын

thanks it helps

@gwtuts4061 Жыл бұрын

Sigma solution - print function in python : # Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def hasCycle(self, head: Optional[ListNode]) -> bool: if head is not None: # print(head.next) will automatically tell if it has # cycle or not. so use it to get answer... # it prints as Error - Linked list has cycle a = str(head.next) if a[0] == "E": return True return False

@cloud-vietnam 2 жыл бұрын

Thanks!

@UKMatt32 Жыл бұрын

I’m not sure if my solution is best practice but instead of using hashing I just set the value of visited nodes to be a value outside of their specified range. Then, if node.next’s value was equal to this “visited” value, there was a cycle. If it doesn’t reach any visited nodes there is no cycle and it returns false. My submission was faster than 96% and better memory than 98% roughly