[LeetCode] Challenge log 142

Posted on | Edited on |

142. Linked List Cycle II

Algorithm:

  1. find the loop and record where slow and fast hit
  2. set slow = head
  3. start traverse again, until the pointers hit again

Analysis:

  1. When they first hit, fast is x steps ahead of slow, where x = k * len(loop).
  2. So in the second traverse, when slow first enter the loop, fast is exatcly k circles ahead and hit slow again.

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Note: Do not modify the linked list.

Follow up:
Can you solve it without using extra space?

Soulution:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head: return None
        
        # find loop and note that pos[where they hit] - pos[head]  = k*len(loop)
        loop = False
        slow = fast = head
        while fast.next and fast.next.next:
            fast = fast.next.next
            slow = slow.next
            if slow == fast:
                loop = True
                break
        if not loop: return None
            
        # find entry
        fast = slow
        slow = head
        while slow != fast:
            fast = fast.next
            slow = slow.next
        return slow
0%