Linked List Cycle - Leetcode 141

🚀 neetcode.io/ - Get lifetime access to every course I ever create!
Checkout my second Channel: / @neetcodeio
🥷 Discord: / discord
🧑‍💼 LinkedIn: / navdeep-singh-3aaa14161
🐦 Twitter: / neetcode1
📷 Instagram: / neetcodeio
🎵 TikTok: / neetcode.io
#coding #neetcode #python

[@dotmashrc]

It made no sense till I read the comments, you should probably explain why that trick works and the fact that the pointers are meant to start together not the arbitrary way they do in the video.

[@user-su9vz7ww6p]

He has a video on main channel with great explanation, it's a bit hard to explain it in shorts tho

[@divyanshsingh6668]

If the slow poiner is ahead of fast pointer won't they evetually meet even if no cycle?

[@m0nny523]

if theres no cycle the slow pointer will never be in front of the fast pointer

[@user-rj1gs4yn8r]

The slow pointer starts out behind the fast pointer.

[@Fs3i]

The fast pointer will reach the end of the list. That means there are no cycles.

[@gusthomas6872]

@@user-rj1gs4yn8rthis seems to be a key point of information not mentioned in the video

[@m0nny523]

video is a little confusing cuz he never explains how the fast/slow pointers r initialized and how they move

[@doug744]

I would recommend explaininng where the two pointers start

[@moyndebs6759]

The way I understand it.
if Slow Fast (So Cycle Found)
Only works if sorted or if you use a hashmap to track the count of both pointers
Or if not sorted then if they Slow == Fast (cycle found)
Fast: 2 - 4 - 1 (meet at 1)
Slow: 4 - 5 - 1 (meet at 1)
Correct me if I'm wrong 🙏

[@Ayooluwaigandan]

Sounds like the tortoise and hare solution I saw on Joma techs video

[@abodora532]

if there is a cycle
the fast will exceed the slow and traverse the cycle and eventually meet the slow pointer
u can ask chat gpt
why the fast and slow pointer work for detecting cycles.

[@michaelroditis1952]

how can we find the start of the loop?
Edit: If my math is right I figured it out.
Let's assume you reach the start of the loop after "a" nodes. When the slow pointer enters the loop, the fast pointer will be "a" steps in front of the slow one. Let's assume that the fast pointer is "b" nodes behind the slow, which means that the loop is "a"+"b" nodes. After "b" steps, the two pointers will meet. That means that after "a" steps the slow pointer will be at the beginning of the loop. If we start a second slow pointer at the beginning, then both slow pointers will meet each other after "a" steps. So the beginning of the loop will be at the meeting point.

[@davea136]

Imagine the scenario where you are using a 21st century computer and have a linked list structure with SO MANY members that you are worried about using no extra space (except 2 pointers.) "My linked list has 8 billion nodes." Lord spare me.
At a certain point these get ridiculous.

[@janekschleicher9661]

On modern computers linked lists make just no sense anymore. I think, the last time I used it were in the 90s. There, of course, arbitrary, non predictable RAM access was quite fast compared to CPU speed. Now you need data structures that respects the multiple level caches and have (for CPU) predictable memory addresses.
Of course, linked lists are still used in databases, but there you usually will have the meta structure (indexes etc) in memory as you can't just hop arbitrary around.
Linked lists are nice from theoretical point of view, but close to every other data structure makes more sense.

[@ceciljoel9577]

Another solution iterate over all element and check if the next node is value is already in hashset and add if its not and if it does we. Found a cycle

[@PurpleDaemon_]

It's O(n) space

[@NabeelFarooqui]

That's what he explains first in the video

[@deemon710]

Maybe I'm misunderstanding what a "cycle" is but... wouldn't this setup ALWAYS land both pointers on the same 5th spot?

[@keivanshamlu]

what if as we go on, we assign null to the last nodes next, then when we reached a node with null next pointer we have the answer

[@martinsolorzano9071]

So if you hadn't seen the solution to this problem, is this something you would've thought up on your own?

[@newuser689]

Hash set yes. Floyd’s algorithm? Probably only if you’ve seen it before

[@mdahsanraza]

I found out this is something some mathematician say down found a solution after at a minimum a year!!

[@harryconcat]

Yo I just search for this and you made a vid about it. For those who didn't know what this algorithm called -> Hare-Tortoise algorithm
And lots of video explain how it works.

[@alexsherzhukov6747]

Given ~head~,…
Yeah thats not gonna happen lmao

[@NeetCode]

😔

[@yugjha6798]

Wow

[@beboba2498]

Absolutely incorrect explanation

[@obungi]

fel