leetcode-ll

142. Linked List Cycle II.py

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

class Solution:
    """
    Thought Process: 
        We use hashmap to store node we visted already, if current node in the hashmap, it mean there's cycle and it's first node starting a cycle.
        If there is no cycle, return None 
    s=f=head
    while f.next and f.next.next:
        s = s.next
        f = f.next.next
        if s==f:
            return s
            
       Similar to 287. Find the Duplicate Number (In array)
    """
    def detectCycle(self, head: ListNode) -> ListNode:
        """
        floyd's algorithm
            step1:先找有沒有cycle用slow and faster two pointers, 找到cycle retur None 且記得終止迴圈
            step2:找到cycle把slow, 再指回head, 然後slow and fast用同樣速度一起前進, 一定會走到一起.
        T:O(n)
        S:O(1)
        """
        s = f = head
        is_cycle = False
        while f and f.next:
            s = s.next
            f = f.next.next
            if s == f:
                is_cycle = True
                #有cycle要記得打斷迴圈不然會TLE跳不出來迴圈
                break
        if not is_cycle:
            return None
        
        s = head
        while s!=f:
            s = s.next
            f = f.next
        return s
    
    def detectCycle(self, head: ListNode) -> ListNode:
        visited = set([])
        cur = head
        while cur:
            if cur in visited:
                return cur
            visited.add(cur)
            cur = cur.next
        return None