[Python 3] LEETCODE 141. Linked List Cycle

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        fast=head
        slow=head
        while fast and fast.next:
            fast=fast.next.next
            slow=slow.next
            if fast==slow:
                return True
        return False

 

플로이드의 토끼와 거북이 알고리즘 (Floyd's Tortoise and Hare Algorithm)을 이용하였다.

플로이드의 토끼와 거북이 알고리즘이란,  Cycle이 존재하는 링크드 리스트에서 토끼와 거북이가 있고, 토끼는 한 번에 두 칸씩, 거북이는 한 번에 한 칸씩 움직인다고 하자.

둘이 만났을 때 거북이를 시작점으로 옮기고, 토끼와 거북이 둘 다 한칸씩 이동시키면, 그 자리 사이클의 시작점에서 다시 만난다는 논리이다. 

 

신기한 알고리즘이다!