Linked List Cycle (LeetCode 141) | Full solution with demo | Floyd Warshall

No video

Linked List Cycle (LeetCode 141) | Full solution with demo | Floyd Warshall | Study Algorithms

Рет қаралды 10,773

Күн бұрын

A really interesting problem where you are required to determine if there is a cycle in a linked list. A loop/cycle is formed if one of the pointers in the linked list points to an internal node in the same list. There are a lot of ways to solve this problem and hence it is very important for interviews. The video explores how you can use a hash table to keep a track of unique nodes and then it demonstrates how the hare tortoise algorithm actually works. A dry-run of code in JAVA is also included.
Chapters:
00:00 - Intro
01:29 - Problem statement and description
03:46 - Brute Force approach to detect a cycle
07:55 - Idea behind an efficient approach (Rabbit/Tortoise method)
10:40 - Efficient solution (Floyd Warshall algorithm)
12:42 - Dry-run to detect cycle
15:02 - Final Thoughts
📚 Links to topics I talk about in the video:
Linked List: • Linked List Data Struc...
Traversing Linked Lists: • Traversing a Linked Li...
Double Linked Lists: • Double Linked List Dat...
Linked Lists playlist: • Linked Lists
📘 A text based explanation is available at: studyalgorithms.com
Problem on LeetCode: leetcode.com/problems/linked-...
Code on Github: github.com/nikoo28/java-solut...
Test-cases on Github: github.com/nikoo28/java-solut...
📖 Reference Books:
Starting Learn to Code: amzn.to/36pU0JO
Favorite book to understand algorithms: amzn.to/39w3YLS
Favorite book for data structures: amzn.to/3oAVBTk
Get started for interview preparation: amzn.to/39ysbkJ
🔗 To see more videos like this, you can show your support on: www.buymeacoffee.com/studyalg...
🎥 My Recording Gear:
Recording Light: amzn.to/3pAqh8O
Microphone: amzn.to/2MCX7qU
Recording Camera: amzn.to/3alg9Ky
Tablet to sketch and draw: amzn.to/3pM6Bi4
Surface Pen: amzn.to/3pv6tTs
Laptop to edit videos: amzn.to/2LYpMqn
💻 Get Social 💻
Follow on Facebook at: / studyalgos
Follow on Twitter at: / studyalgorithms
Follow on Tumblr at: / studyalgos
Subscribe to RSS feeds: studyalgorithms.com/feed/
Join fan mail: eepurl.com/g9Dadv
#leetcode #programming #interview

Пікірлер: 71

@sheldoncooper7990 9 ай бұрын

You are just greek god of teaching complex stuff in the simplest way possible!! God bless for your efforts.

@nikoo28 9 ай бұрын

haha...will try my best to keep bringing such content

@debottamyoutube 5 ай бұрын

What an explaination. Calm, cool, smiling, no use of complex words, it was like listening to a story. ❤ Subscribed!!!

@GrowWithHare Ай бұрын

Wow, I can't imagine you explained this problem so well. Thanks a lot bhaiya❤😊

@JammUtkarsh 10 ай бұрын

I must say you speak very politely and your explanation is LIT 🔥 🔥 🔥 🔥. I personally find your videos better NeetCode. Hope your channel grows!!!💜

@nikoo28 9 ай бұрын

As long as you understand things, it is all that matters. 🙂

@pranavm9301 6 ай бұрын

Very good explanation. in while condition, slow != null is not required because slow pointer is always behind fast and if there is a null, it's detected by fast pointer and we break out of loop

@hamdasalam4373 Ай бұрын

What an awesome explanation.Sir could you please come up with the continuation of the video on how to find the node at which the cycle occurs?, will be of great help

@akashchakrabortty2431 Жыл бұрын

Thanks Nikhil, for explaining the approach so nicely

@safar19899 Жыл бұрын

Great explanation! Thank you!

@matthewzarate8851 2 ай бұрын

Your entire linked list playlist is amazing Nikhil!

@kayathrivenkatesan7712 3 ай бұрын

thank u so much .i have been searching only for ur solution for evry prblm and go to other videos only if ur video is not present.ur videos and visuals bring more interest for me to solve problems

@alisheheryar1770 4 ай бұрын

You hoped you simplified the solution. And yes you are Sire! you indeed simplified it. I hope i could give you a cookie.

@CodingSquirrel777 Жыл бұрын

Thank you AGAIN!!

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

Great explanation 🔥

@user-ei4qc7ss6w 5 ай бұрын

such a simple explaination

@JH-wy2pc 8 ай бұрын

Superb explanation

@hunorvadasz-perhat6001 Жыл бұрын

Very nice and easy to understand explanation! Subscribed! 😄

@nikoo28 Жыл бұрын

thank you for subscribing.. :)

@mayankbadika3101 5 ай бұрын

Great explanation :)

@ashokrajan9401 2 жыл бұрын

Very nice explanation Brother

@arupbasak919 Жыл бұрын

Really I love your way of explanation...Also it made me easy to understand..

@nikoo28 Жыл бұрын

Happy to help

@AadeshKulkarni 5 ай бұрын

Beautiful baba!

@Sai-fn4lq 10 ай бұрын

Thanks a ton sir !! subbed🙂

@nikoo28 9 ай бұрын

Thanks for the sub!

@TuringTested01 Жыл бұрын

youre an amazing tutor nikhil! Cheers

@nikoo28 Жыл бұрын

thanks for the comment

@divyaawasthi8286 9 ай бұрын

Nikhil Bhai, Thankyou so much i got clarity on LL through your videos only...Very clear explanation you are doing great job Brother Proud of you.

@nikoo28 9 ай бұрын

thanks so much

@parthmodi2028 5 ай бұрын

Ur vidoes are really helpful. Pls cover more problems

@nikoo28 4 ай бұрын

a new video every week.

@chakravarthybatna1589 11 ай бұрын

your channel is underated, your videos are amazing bro , awesome explanation please keep posting new video's in english

@nikoo28 11 ай бұрын

I will try my best

@SATYAMTIWARI-ps3wb 10 ай бұрын

superb explanation boss

@nikoo28 9 ай бұрын

Keep watching

@jayaveeran1 Ай бұрын

Hi Nikhil, thanks for the amazing video, just one query do we really need the condition slowPtr!=null on the while loop ?

@shraddhajain8935 2 жыл бұрын

Hey! can you explain the while condition a bit more? For me it is failing for a test case like '[-21,10,17,8,4,26,5,35,33,-7,-16,27,-12,6,29,-12,5,9,20,14,14,2,13,-24,21,23,-21,5] -1' when it comes to a point where 'fast.next.next' is None. It is working when we are adding a null check for fast.next.next as well

@TechTribers Ай бұрын

very good explanation & easy to understand . Jus wanted to ask which application you use for writing in ipad like (goodnote ,notability)

@nikoo28 Ай бұрын

GootNotes 6

@johncho9160 6 ай бұрын

can you pls explain what the purpose of fastPtr.next != null condition in the while loop? i understand that if slowPtr or fastPtr is null then it is not a cycle but why the third condition?

@nikoo28 5 ай бұрын

we want to make sure that we don't hit null pointer. It is not necessary that the linked list has a cycle for sure

@rodba1393 5 ай бұрын

thank you so much you are the best!!!!!

@preetijavali6595 5 ай бұрын

Hi Thanks fo the video. Can you explain why while loop has 3 conditions? if fast pointer reaches null, its already proven that it doesnt have loo. also fast pointer will always reach null first, so why check for slow pointer is null or not? and why check fast pointer.next is null?

@nikoo28 5 ай бұрын

you are right...we can get rid of slowPtr check in the while loop.

@preetijavali6595 5 ай бұрын

@@nikoo28 Thank you.

@priyanshgarg1292 Жыл бұрын

WHY NOT WE ARE moving hare with 3x or 4x or 5x etc... speed then also it will come in loop why only 2x speed?

@nikoo28 Жыл бұрын

While you could potentially use a higher speed like 3x, 4x, or 5x, using a speed of 2x ensures that the hare and tortoise pointers will eventually meet if there is a cycle. Using a higher speed than 2x might not guarantee this outcome. Let's explore the reasoning behind using a 2x speed for the fast pointer: - Balanced Progress: Moving the fast pointer at 2x the speed of the slow pointer creates a balanced progression. This ensures that the fast pointer catches up to the slow pointer at a steady rate. - Guaranteed Intersection: In a linked list with a cycle, the fast pointer will eventually enter the cycle. Since the cycle has a finite length, the fast pointer will "lap" the slow pointer (that's moving at a 1x speed) before they meet again. - Avoiding Overlooking Cycles: If you were to use a higher speed for the fast pointer, like 3x or 4x, you might inadvertently overshoot or skip over some cycles. This is because the fast pointer might move through multiple complete cycles while the slow pointer is still traversing through a single cycle. - Minimal Tracking: Using a 2x speed minimizes the number of steps required to find a cycle. While increasing the speed might lead to faster movement, it doesn't guarantee a more efficient cycle detection process.

@vaibhavkgote 11 ай бұрын

what application do you use to write in tab?

@nikoo28 11 ай бұрын

That would be Goodnotes 6.

@vaibhavkgote 10 ай бұрын

@@nikoo28 Thank you !

@infinite639 Жыл бұрын

I can run the code on Leetcode but But i want to run it on my local IDE as a normal input output program You have only written test cases

@nikoo28 Жыл бұрын

You can just copy the test case inside the main method and it will work

@kidoo1567 10 ай бұрын

Is this approach correct.. change the value of every node we are traversing as max integer. And check if we reach the node max integer again while traversing print true😅

@nikoo28 9 ай бұрын

that works too, but then you are modifying the actual list. confirm with your interviewer if you are allowed to make changes.

@kidoo1567 9 ай бұрын

Yeah

@kalyanamvenumadhav2245 Жыл бұрын

How to display value instead of true and false

@nikoo28 Жыл бұрын

Once you identify the node you stop at, you can store it's value somewhere and then return it.

@sharabugnanesh3098 10 ай бұрын

I can't find the solution for this thing "Where to find the cycle first"😢

@nikoo28 9 ай бұрын

this: kzfaq.info/get/bejne/b5uKmdiguKe5gH0.html

@shivangchauhan820 11 ай бұрын

It would be good If you have made this video in hindi as there are not much viewers who don't understand hindi.

@nikoo28 11 ай бұрын

i will try to add subtitles in other languages

@abuyousuf7281 7 ай бұрын

Sorry bro! Your solution exceeded the time limit of leetcode constraints. This approach is not accepted in Leetcode.

@nikoo28 7 ай бұрын

That can’t be possible, did you check the code in the github link available in the description? It passes on LeetCode

@abuyousuf7281 7 ай бұрын

@@nikoo28 sorry brother about my last comment. Yes this approach is good enough but I tried your same concept but that showed time limit exceeded. I want to let you know that I used Java. But after that I had seen another video which is same approach but differently. Like: ListNode slow = head; ListNode fast = head.next;a while(){ .... slow = slow.next; fast = fast.next.next; } Return true; And Buddy that passed the time limit constraint.

@abuyousuf7281 7 ай бұрын

@@nikoo28 Don't get me wrong sir, You’ve done an amazing job. Just wanted to let you know I've failed to pass my time limit.