LeetCode 141 - Linked List Cycle

단일 연결 리스트(Singly Linked List)가 주어졌을 때, 리스트 내부에 순환(Cycle) 구조가 존재하는지 확인하는 Easy 문제다. 추가적인 노드 방문 집합(Set)을 쓰지 않고, 이동 속도가 다른 두 개의 포인터(slow, fast)를 활용하여 O(1) 공간 복잡도로 사이클을 탐지했다.

문제 링크 & 설명

문제 링크: 141. Linked List Cycle
요약: 주어진 연결 리스트의 head에서 출발하여 어떤 노드를 계속 따라갈 때 다시 방문하는 순환 고리가 존재하면 True, 리스트 끝(None)에 도달하면 False를 반환한다.

노드를 탐색하며 방문한 노드를 해시 테이블(Set)에 저장하는 방법은 O(n)의 추가 메모리를 소모한다. 반면 서로 다른 속도로 이동하는 두 포인터를 활용하면 사이클이 있을 때 빠른 포인터가 느린 포인터를 반드시 따라잡는다는 성질(플로이드의 토끼와 거북이 알고리즘)을 이용할 수 있다.

접근 방법

slow 포인터는 한 번에 한 칸씩, fast 포인터는 한 번에 두 칸씩 전진한다.

slow = head
fast = head

while fast and fast.next:
    slow = slow.next
    fast = fast.next.next

    if slow == fast:
        return True

return False

포인터 초기화: 두 포인터 모두 head에서 시작한다. 리스트가 비어 있거나 노드가 1개뿐인 경우 순환이 불가능하므로 즉시 False를 반환한다.
반복 이동: fast와 fast.next가 None이 아닌 동안 slow는 1칸(slow.next), fast는 2칸(fast.next.next)씩 전진한다.
만남 감지: 만약 리스트에 순환이 존재한다면, 루프 안에서 두 포인터 간의 상대적 거리가 매 턴마다 1씩 좁혀져 결국 slow == fast로 만나게 된다.
종료 조건: 리스트 끝에 도달하여 fast 또는 fast.next가 None이 되면 사이클이 없으므로 루프를 빠져나와 False를 반환한다.

복잡도 분석

시간 복잡도: O(n)
- 사이클이 없다면 fast 포인터가 n/2번 이동 후 리스트 끝에 도달한다. 사이클이 있다면 진입 후 최대 사이클 길이 내에서 두 포인터가 만나므로 선형 시간에 종료된다.
공간 복잡도: O(1)
- 추가적인 해시 셋이나 배열 없이 두 개의 포인터 변수만 사용한다.

구현 코드

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


class Solution:

    def hasCycle(self, head) -> bool:
        if not head or not head.next:
            return False

        slow = head
        fast = head

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

            if slow == fast:
                return True

        return False

요약 및 회고

연결 리스트의 사이클 탐지에서 플로이드 알고리즘은 공간 복잡도를 O(1)로 줄일 수 있는 대표적인 패턴이다. 매 단계마다 빠른 포인터가 느린 포인터와의 거리를 1씩 좁히기 때문에 사이클이 존재한다면 무한 루프 없이 반드시 유한한 단계 안에 만난다는 불변 조건이 보장된다.