LeetCode 141: Linked List Cycle — 단계별 시각적 추적

Source: Dev.to

문제 설명

연결 리스트의 head가 주어졌을 때, 리스트에 사이클이 존재하는지 판단합니다. 사이클은 next 포인터를 계속 따라가다 다시 같은 노드에 도달할 수 있을 때 존재합니다.

접근법

플로이드 사이클 탐지 알고리즘(일명 “거북이와 토끼” 기법)을 사용합니다. 두 포인터가 서로 다른 속도로 리스트를 순회합니다:

• 느린 포인터는 한 번에 한 단계씩 이동합니다.
• 빠른 포인터는 한 번에 두 단계씩 이동합니다.

사이클이 있으면 빠른 포인터가 결국 느린 포인터와 만나게 됩니다. 사이클이 없으면 빠른 포인터가 리스트의 끝(None)에 도달합니다.

복잡도 분석

• 시간: (O(n)) – 각 노드를 최대 상수 횟수만큼 방문합니다.
• 공간: (O(1)) – 리스트 크기에 관계없이 두 개의 포인터만 사용합니다.

참고 구현 (Python)

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

        slow = head
        fast = head.next

        while slow != fast:
            if not fast or not fast.next:
                return False
            slow = slow.next
            fast = fast.next.next

        return True

인터랙티브 시각화

Open interactive visualization – TraceLit을 사용해 각 라인을 단계별로 살펴볼 수 있는 인터랙티브 시각화 도구입니다. LeetCode 연습에 활용해 보세요.