LeetCode 142 | Linked List Cycle II | Algorithm Explained (Java + Whiteboard)

[@luvingskittles]

From a more mathematical perspective: Let x = distance from starting node to node where cycle begins Let y = distance from node where cycle begins to where fast and slow pointer meets Let c = length of the cycle Let n = number of cycles travelled When slow and fast meet: slow pointer travelled x + y distance fast pointer travelled 2(x + y) distance -> extra distance travelled is a multiple of cycle length -> 2(x + y) - (x + y) = nc -> x + y = nc (also means slow travelled distance of nc) -> x = nc - y We can infer than if slow pointer continues travelling from (x + y), after x more steps it will reach the cycle starting point. Which is why if we move head at the same rate as slow in the second part, their meeting point equals to start of cycle.

[@abhiram6087]

bro! according to Floyd's Cycle detection you found out that there is a cycle but how did you know that "intersect" and "start" would be same nodes away from intersection.

[@javaguru7453]

kzbin.info check this too

[@LeetCodeSimplified]

NeetCode has a video explaining it in detail: kzbin.info/www/bejne/rZu8n62hds2WhM0

[@mikeyyychang8402]

Since. (2S = F) consider the part from start - cycle point = A, cycle point- intersect = B, intersect - cycle point = c then slow trival A + B fast travel A + (B+C) * N + B (B+C) is one cycle and * N number we travel the cycles from 2S = F we know (B+C)*N = a + b from (B+C)*N = a + b if we remove B from each side B*(N-1) + C*N = A. then A must be equal to C or eqaul to X*C + Y * B where (X - Y = 1) In other words A mod(b+c) = C, As a result when we travel from start to point takes A to cycle points and Intersect to cycle points will be same distance or travel M cycles then reach to cycle points (from A mod(b+c) = C); (thats is why we set 1 ptr at start and 1 at intersect and trival at same rate.)

[@tiakimx]

What is 2S=F?

[@mikeyyychang8402]

@@tiakimx travel speed for slow ptr and fast ptr

[@chenjiewu9927]

This is really clear explanation, thank you!

[@sankalpvk18]

I'm not sure why it works but this seems like the best solution out there. Thanks for the help man. Appreciate it.

[@aushoroup9735]

Hello brother! You explained well, but it's my request to prove the logic of second part mathematically if possible. That is how can you say that the first node of the loop is exactly the same distance apart from the head as.......................................... Please prove this part of your logic mathematically. It's my request. Thanks

[@xavierelon]

Ausho Roup the comment below you proved it mathematically. It’s a complicated mathematical proof that took computer scientists a while to come up with

[@myvinbarboza3038]

Xavier Elon Awesome content but it does lack the proof for the second part. kzbin.info/www/bejne/gobQY3R4pqamZ9k

[@gilbertzhuo7185]

@@myvinbarboza3038 a much simpler version is in my channel

[@aushoroup9735]

@@xavierelon Thanks

[@aushoroup9735]

@@myvinbarboza3038 Thanks

[@kapilgarg7758]

Thank you Xavier. I loved this explanation. I was breaking my head for 2 hours on this problem. Your 6 minutes video made my day.

[@xavierelon]

You’re very welcome. Thanks for watching my video

[@javaguru7453]

kzbin.info check this too

[@jamesvick8066]

Nice vid. Thanks for the explanation

[@adamwest9183]

If you're building onto the Linked List 1 given solution: Using fast = head.next, your intersection will always be off by one. Fix this by either: 1) fast = head; 2) while(intersect.next != start) { start = start.next; intersect = intersect.next; }

[@KiraIRL]

Hi. I had a question about the second part of this. Since we increment intersect pointer by one each time, as well as the starting pointer by one each time. If the starting pointer entered the cycle wouldn't we never find the starting point? Or even a node where both pointers are on the same node? Like what would happen if there was an extra node before the beginning of the cycle? It just so happen to be that the length was the same between starting node and the intersection node to the node (7). Isn't the intersect node only 1 node away?

[@xavierelon]

LoveandAbandon draw it out on a piece of paper. Add a node and see what happens. They will always be the same distance from the start of the cycle

[@KiraIRL]

@@xavierelon I just sat down and drew 10 different LL'S on my whiteboard for 10mins. I think I understand. The turtle and hare function sets up where the intersection lies thus also setting up the distance between starting and intersect node to the starting of the cycle. Adding a node changes the intersect node which also changes the length? So no matter how many nodes exist before the cycle. the position of the intersect will always correctly determine the beginning of the cycle. I think I got it? Haha

[@xavierelon]

Yes exactly. You can change the amount of nodes all you want but then you’re also changing the number it takes to find the intersect which will still be the correct number to find the start cycle. I always recommend drawing it out to understand better

[@KiraIRL]

@@xavierelon thank you! I appreciate the help. Please keep doing these, I love your explanation style and your quick video formats

[@xavierelon]

@@KiraIRL thanks man I really appreciate it. I haven't been getting many views so I wasn't sure if these were actually helping people. So good to hear

[@nathann4291]

tnx for posting, whats your tech setup? I assume that's an iPad?

[@xavierelon]

MBP 16' and Ipad Pro

[@akermiyu]

For the second part of the problem where assigned pointer to be head and move both the pointer and fast one step under the while loop, how is it possible that pointer will equal to fast (in order to break out of the loop) if they're moving at the same speed at different positions in the linked list?

[@xavierelon]

Because if there’s a cycle they will eventually be equal. Draw out an example

[@豆子-d9t]

Best clean code

[@mayankrathore7558]

Hi Tried to join ur channel, but it seems to be expires could please share it again

[@lakeman4101]

Thanks Xavier. Could you pls provide a link to the solution?

[@xavierelon]

As in like a Github file?

[@SoftwaresCares]

Excellent! Keep doing it Sir!

[@シリコンバレーエンジニアの日常]

Hi, thank you for the video! Your explanation is very clear! I'm curious. What iPad app are you using?

[@シリコンバレーエンジニアの日常]

I found it is Goodnotes. Thanks!

[@santhoshn31]

Great explanation.

[@javaguru7453]

kzbin.info check this too

[@daviddaniel2845]

I do not understand what cycle mean? 😂

[@kelvincheung7272]

Your explanation is very clear, thanks!

[@xavierelon]

You're very welcome

[@jigyasakodnani]

helped, Thanks alot :)

[@ehsanshams4099]

thanks for the video

[@javaguru7453]

kzbin.info check this too

[@ognimoddd]

Great explanation, thank you.

[@xavierelon]

You’re welcome

[@wheresthebeach0138]

Hey dude, enjoying the short-form content you put out. I've watched this one over quite a few times, but am getting caught at one particular spot -- specifically, in the first part of the question (looking for the intersection point) my logic is slightly different, and it's leading me into an infinite loop, but I'm not sure why. I've tested the code out and it does correctly predict whether or not there exists a loop in the cycle (i.e. Linked List Cycle I problem), but when it finds that intersection point it is different than the one you're finding, and I'm not sure why mine is incorrect. Would appreciate any insight you have! :) def intersection(self, head): slow, fast = head, head.next while slow != fast: if not fast or not fast.next: return None slow = slow.next fast = fast.next.next return slow

[@xavierelon]

Can you post all of your code so I can figure it out?

[@wheresthebeach0138]

@@xavierelon Definitely, thank you!! class Solution: def intersection(self, head): slow, fast = head, head.next while slow != fast: if not fast or not fast.next: return None slow = slow.next fast = fast.next.next return slow def detectCycle(self, head): if not head: return intersectionPoint = self.intersection(head) if not intersectionPoint: return start = head.next while start != intersectionPoint: start = start.next intersectionPoint = intersectionPoint.next return start

[@xavierelon]

​@@wheresthebeach0138 sorry for the delay. I barely use Python so thank you for making me practice lol. This is what I came up with: class Solution: def intersection(self, head): slow, fast = head, head while fast != None and fast.next != None: slow = slow.next fast = fast.next.next if slow == fast: return slow return null def detectCycle(self, head): if head == None or head.next == None: return None intersectionPoint = self.intersection(head) if not intersectionPoint: return start = head while start != intersectionPoint: start = start.next intersectionPoint = intersectionPoint.next return start so what I think you were doing wrong is first you never set the fast and slow to the same node. I drew it out on a whiteboard and your code detects the cycle a node sooner so the reason it is in an infinite loop is because you're moving both the pointers in the second function at the same rate and they will never collide due to being one off. It took me a while to figure this out. Let me know if this answers your question!

[@siddharthb2226]

clear and crisp. Love u . no homo

[@xavierelon]

No homo… :(

[@laughoutmeow]

Dude i dont understand ur intersect function cause the fast pointer is going twice as fast as the slow point which mean it skips some node so your not comparing it to all nodes which means depending on the situation it might miss the intersection

[@xavierelon]

Draw it out. Do an even number intersection (4 or 6 nodes) and an even number intersection (3 or 5 nodes). They will always eventually intersect

[@karteeksunkara826]

Great explanation. Appreciate your time uploading quality content in short video formats.

[@xavierelon]

Karteek Sunkara thank you!