Leetcode - Linked List Cycle II (Python)

October 2020 Leetcode Challenge
Leetcode - Linked List Cycle II # 142

[ojij]

It's either you know or you don't. You can't come up with it at the spot. Loved that part😂.

[LeeK]

Do you use any resources (books, articles, etc) to help you develop the intuition for these tricky problems?

[zzhumash]

Is there any proof that head and slow pointers intersect on start of the cycle? If so, why?

[ClaireChiang]

Hi Tim, a question here. Could we also consider not giving a new variable slow2 and directly moving slow pointer to head? Then the next while condition would be fast !=slow. I'm just not sure about the difference between these two whiles (your "while slow.next" and " while slow !=fast).

[janmichaelaustria]

gahh, i didn't think you could add node classes in a set, derppp

[jordanrowland]

Awesome video, earned a subscription from me!

[hrithikkhandelwal]

Thanks brother!These are helping people a lot

[edwardteach]

# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None

class Solution(object):
def detectCycle(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head:
return

slow = fast = head
while fast and fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
break
else:
return None

while head != slow:
head = head.next
slow = slow.next
if head == slow:
return slow

return slow

[oussamabennabi]

me be like :
after completing the whole video and he says "do not trust me i don't know nothing".

[udayptp]

In your first approach if there are duplicate elements in linked list then you can't add them in set and hence your code will reture curr and that will be wrong output.

[jeremygong]

this problem is actually quite simple and can be mathematically evaluated. that says you can mentally calculate it: 1) assume entry is K steps away from the head, and 2) assume that you have a big enough cycle that has P steps. 3) by the time slow enters cycle, slow travels exactly K steps, and fast travels exactly 2K steps, 4) in cycle space, fast is K steps from the entry, and since now its a loop and the delta "speed" for fast and slow is 1, 5) it will take P-K steps for fast to first impact slow, and by the time, 6) slow traveled P-K steps away from the entry, 7) since its a circle, it also means slow is P-(P-K) = K steps away from the entry, 8) by the impact moment sent another slow, and 9) they will travel K steps to meet each other by the entry. 10)* now if the cycle is not big enough, you will need to prove that int times of P will cover up that delta distance (which is also an easy proof).
Elementary math really.