[LeetCode | Python] 141. Linked List Cycle (Floyd's Cycle Detection Algorithm, 플로이드의 토끼와 거북이 알고리즘)

링크드리스트에 사이클이 있는지 없는지 판단하는 문제이다.

set을 이용하여 간단히 풀 수도 있지만, 

플로이드의 순환 찾기 알고리즘, 플로이드의 토끼와 거북이 알고리즘으로도 풀 수 있는 재밌는 문제였다!

 

풀이1. set 이용

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

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:

        seen = set()
        cur = head
        
        while cur:
            if cur in seen:
                return True
            seen.add(cur)
            cur = cur.next
        
        return False

 링크드리스트를 한번 순회하므로 시간복잡도 O(n),

최대 n 크기의 set()을 사용하므로 공간복잡도 O(n)이다.

 

풀이2. 플로이드의 토끼와 거북이 알고리즘

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

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        
        slow, fast = head, head

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True
        return False

링크드리스트에 사이클이 존재하면,

한 칸씩 이동하는 포인터와 두 칸씩 이동하는 포인터를 만들었을 때

두 포인터가 만나게 된다. 

그렇지 않으면 더 빠른 노드가 끝에 도달하여 while문이 종료되게 된다.

리스트를 한번 순회하므로 시간 복잡도는 O(n),

두 개의 포인터만 필요하므로 공간 복잡도는 O(1)이다.