[Python] 142. Linked List Cycle II

난이도 : medium

 

linked list의 cycle이 시작하는 지점을 return하는 문제.

cycle이 없으면 null return

 

보통 linked list에서 cycle에 관련된 문제는, Floyd's Tortoise and Hare 알고리즘을 사용하여 cycle이 있는지 확인한다.

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = head
        fast = head
        
        while fast and fast.next:    #Floyd's Tortoise and Hare 알고리즘
            slow = slow.next
            fast = fast.next.next
            
            if slow == fast:         # 두 pointer가 만나면, cycle이 있다는 의미
                break
        
        if not fast or not fast.next: #fast나 fast의 뒤가 없다 :cycle이 없음
            return None
        
        slow = head
        while slow != fast:          #두 pointer가 같은 속도로 이동할 때 만나는 지점이 cycle의 시작점
            slow = slow.next
            fast = fast.next
        
        return slow

1. Floyd's Tortoise and Hare 알고리즘을 사용하여, slow와 fast가 만나는지 확인
2. fast가 없거나, fast.next가 없다면 tail이 있다는 것. cycle이 없으니까 None을 return
3. slow를 head로 다시 설정 후, 두 pointer를 한 칸씩 움직이다 보면 만나는 지점이 cycle의 시작점이다.
4. 그 때의 slow를 return

Runtime : 45ms (65.69%)

Memory : 19.70MB (50.76%)