LeetCode

LeetCode 141 Linked List Cycle 풀이: 플로이드의 순환 탐지 알고리즘

2026년 9월 8일

작성·코드 검증: solve together · 작성 언어: Python

0. 문제 링크와 출처

문제: 141. Linked List Cycle
출처: LeetCode
자체 판단 난이도: Level 3

연결 리스트라는 자료구조의 연결 관계를 이해하고, 플로이드의 순환 탐지 알고리즘을 적용해야 하는 문제다. 구현은 간단하지만 자료구조와 알고리즘 이해가 필요하므로 Level 3으로 판단했다.

1. 문제 요약

연결 리스트의 시작 노드 head가 주어질 때, 리스트에 순환이 있으면 true, 끝까지 도달할 수 있으면 false를 반환한다.

문제 설명의 pos는 꼬리 노드가 연결되는 위치를 설명하기 위한 값일 뿐, 함수의 인자로 전달되지 않는다. 그래서 배열처럼 값을 비교하는 것이 아니라 실제 노드의 next 연결을 따라가며 같은 노드를 다시 만나는지 확인해야 한다.

예를 들어 1 -> 2 -> 3 -> 2처럼 세 번째 노드가 두 번째 노드를 가리키면, 이후에는 2 -> 3 -> 2가 반복되므로 순환이 있다. 1 -> 2 -> None이라면 리스트의 끝에 도달하므로 순환이 없다.

2. 문제 해결에 사용되는 알고리즘이나 자료구조 설명

핵심 관찰

순환이 없는 연결 리스트에서는 모든 포인터가 결국 None에 도달한다. 반대로 순환이 있다면 리스트 안의 유한한 구간을 계속 반복해서 지나가게 된다.

이 성질을 이용해 두 포인터를 사용한다.

slow: 한 번에 한 칸 이동한다.
fast: 한 번에 두 칸 이동한다.

순환이 없다면 fast가 먼저 None이 된다. 순환이 있다면 두 포인터 모두 순환 구간에 들어가고, fast가 매번 한 칸씩 더 빠르게 이동하므로 결국 같은 노드를 가리키게 된다.

포인터가 가리키는 노드의 값이 같다는 뜻이 아니라, 같은 노드 객체를 가리킨다는 뜻으로 비교해야 한다. 그래서 Python에서는 slow == fast보다 slow is fast를 사용한다.

플로이드의 순환 탐지 알고리즘

slow와 fast를 모두 head에서 시작한다.
fast와 fast.next가 존재하는 동안 두 포인터를 이동한다.
이동 후 두 포인터가 같은 노드라면 순환이 있으므로 True를 반환한다.
fast가 None에 도달하면 순환이 없으므로 False를 반환한다.

3. 문제 해결 코드 (Python)

class Solution:
    def hasCycle(self, head: 'ListNode | None') -> bool:
        slow = head
        fast = head

        while fast is not None and fast.next is not None:
            slow = slow.next
            fast = fast.next.next

            if slow is fast:
                return True

        return False

fast가 두 칸 이동하려면 fast와 fast.next가 모두 존재해야 하므로, 반복 조건에서 두 값을 먼저 확인한다. 노드를 최대 몇 번 순회하더라도 각 이동은 상수 시간이므로 시간 복잡도는 O(n)이다. 방문 집합이나 별도의 리스트를 만들지 않으므로 추가 공간 복잡도는 O(1)이다.

4. 오답 접근과 반례

노드의 값만 비교하기

연결 리스트에서는 서로 다른 노드가 같은 값을 가질 수 있다. 그래서 값이 같다는 이유만으로 순환이라고 판단하면 안 된다.

1 -> 2 -> 1 -> None

위 리스트의 첫 번째 노드와 세 번째 노드는 값이 모두 1이지만 서로 다른 노드이며, 끝에 None이 있으므로 순환이 아니다. 순환 판별은 값이 아니라 노드 객체의 동일성을 확인해야 한다.

`fast.next`를 확인하지 않고 두 칸 이동하기

fast만 확인하고 fast.next.next를 바로 접근하면, 마지막 노드에서 fast.next가 None인 경우 오류가 발생한다. 이동 전에 fast와 fast.next를 모두 검사해야 한다.

방문 집합을 무조건 사용하는 방식

방문한 노드를 set에 저장하는 방식도 정답을 구할 수 있지만, 노드 수에 비례하는 O(n) 공간이 필요하다. 문제의 추가 조건인 O(1) 메모리를 만족하려면 두 포인터만 사용하는 플로이드 알고리즘이 더 적합하다.

복사해 실행할 테스트

로컬 실행 시 아래 ListNode 보조 클래스를 풀이 코드보다 먼저 두고 assert를 뒤에 붙인다. 순환과 비순환 리스트를 모두 검사한다.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

a, b, c = ListNode(3), ListNode(2), ListNode(0)
a.next, b.next, c.next = b, c, b
assert Solution().hasCycle(a) is True

x, y = ListNode(1), ListNode(2)
x.next = y
assert Solution().hasCycle(x) is False

5. 공식 예제와 추가 검증

LeetCode 공식 예제 3개와 순환 판별에 필요한 경계 사례를 확인했다.

예제	기대 출력	확인 결과
`head=[3,2,0,-4], pos=1`	`True`	통과
`head=[1,2], pos=0`	`True`	통과
`head=[1], pos=-1`	`False`	통과

pos는 테스트 데이터에서 연결 구조를 만드는 데 사용되며, hasCycle 함수에는 전달되지 않는다.

추가 검증 1: 빈 리스트

입력: head = None
기대 출력: False
확인 결과: 통과
검증 목적: 시작 노드가 없는 경우의 경계 처리 확인

추가 검증 2: 자기 자신을 가리키는 한 노드

입력: 1 -> 1
기대 출력: True
확인 결과: 통과
검증 목적: 가장 짧은 순환 구조 확인

추가 검증 3: 값은 같지만 순환이 없는 리스트

입력: 1 -> 2 -> 1 -> None
기대 출력: False
확인 결과: 통과
검증 목적: 노드 값이 아닌 객체 동일성을 비교하는지 확인

추가 검증 4: 긴 꼬리 뒤의 순환

입력: 1 -> 2 -> 3 -> 4 -> 2
기대 출력: True
확인 결과: 통과
검증 목적: 순환에 진입하기 전의 비순환 구간도 처리하는지 확인

6. 다른 풀이 방식 검색 및 비교

Linked List Cycle 공식 문제는 next 포인터를 따라 같은 노드에 다시 도달하는지 판별하도록 정의한다.
AlgoMonster의 설명은 한 칸 이동 포인터와 두 칸 이동 포인터의 만남을 이용한 순환 탐지를 설명한다.

방문한 노드를 set에 저장하면 현재 노드를 이미 방문했는지 직접 확인할 수 있다. 이 방식은 구현이 직관적이고 시간 복잡도는 O(n)이지만 공간 복잡도도 O(n)이다. 이 글에서는 문제의 O(1) 추가 공간 조건을 만족하기 위해 방문 기록 대신 포인터의 속도 차이를 사용했다.

마무리

Linked List Cycle은 연결 리스트에서 끝에 도달하는 경우와 순환 구간을 반복하는 경우를 두 포인터의 움직임으로 구분하는 문제다. slow는 한 칸, fast는 두 칸씩 이동시키고 같은 노드에서 만나는지만 확인하면 방문 집합 없이 O(n) 시간과 O(1) 공간으로 해결할 수 있다.