Short Python solution: 8 lines


  • 3
    class Solution(object):
        def detectCycle(self, head):
            slow, fast = head, head
            while True:
                if fast == None or fast.next == None: return None
                slow = slow.next; fast = fast.next.next
                if slow == fast: break
            while head != fast:
                head = head.next; fast = fast.next
            return head
    

  • 0
    P

    I understand the detection part, but
    why can you make sure that when node head == node fast, it is the start of the linked list cycle?


  • 4
    L

    @pjerryhu Hello,

    Let's say, the first node is node 0, the cycle starts at node L, and the length of the cycle is C;
    Moreover, after t steps, fast catches slow.

    Now we know that fast totally traveled 2t nodes, and slow traveled t nodes

    Then we have:
    2t - t = nC (where n is an positive integer.)
    i.e. t=nC

    Now, think about that, at step t, if we travels L more steps, where are we?
    i.e. if we travel L+t = L + nC steps in total, where are we?

    Absolutely, at the start of the cycle, because we have covered the first L nodes once and the entire cycle n times.

    So, if we travel L more steps at time t, then we get the start of the cycle.

    However, how can we travel exactly L step?
    The answer is to use an other pointer to travel from node 0, and when they meet together, it is exactly L steps and both of them are at the start of the cycle.

    Hope that help :)


  • 0
    P

    @LostSummer233 Thank you. This is very helpful


  • 0
    W

    Some really good explanation on youtube :D


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.