[LeetCode] 142. Linked List Cycle II

Problem : https://leetcode.com/problems/linked-list-cycle-ii/

Hash table based solution:

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

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        memo = set()
        
        while head:
            if head in memo:
                return head
            
            memo.add(head)
            head = head.next
            
        return head

Fast and slow pointer solution:

Space complexity = O ( 1 )

Firstly, pointer P1 moves 2 times faster than P2. The linked list has cycle if P1 meets P2

Assume P1 and P2 meet at node P. Because P1 moves 2 times faster P2, A + B + C + B = 2 * (A + B)

So A = C.

Secondly, move pointer P1 back to the head of linked list. Then move P1 and P2 with same speed. P1 and P2 must meet again at node Q which is the node where the cycle starts.

      Q       P

--A---|---B---|
      |       |
      |       |
      |       |
      |---C---|

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

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
     
        p1 = p2 = head
        
        while p1 and p1.next and p2:
            p1 = p1.next.next
            p2 = p2.next
            
            if p1 == p2:
                # find the cycle
                p1 = head
                
                while p1 != p2:
                    p1 = p1.next
                    p2 = p2.next
                
                return p1
        
        
        return None