Linked List Cycle

연결 리스트의 끝은 보통 null이다. 따라서 리스트를 순회하는 코드는 언젠가 null을 만나 멈춘다.

A → B → C → null

하지만 어떤 노드의 next가 앞에서 방문한 노드를 다시 가리키면 끝에 도달할 수 없다.

A → B → C → D -> B -> C ...

이 문제는 연결 리스트를 따라가며 이러한 순환이 존재하는지 판별하는 문제다.

`null`을 찾는 대신 재방문을 찾아야 한다

순환이 없는 리스트라면 한 방향으로 이동할 때 같은 노드를 두 번 방문하지 않는다. 반대로 같은 노드를 다시 방문했다면 이후에도 같은 경로를 반복하게 되므로 순환이 존재한다.

이 정의를 그대로 코드로 옮기면 방문한 노드를 Set에 저장할 수 있다.

function hasCycle(head: ListNode | null): boolean {
  const visited = new Set<ListNode>();
  let current = head;

  while (current !== null) {
    if (visited.has(current)) {
      return true;
    }

    visited.add(current);
    current = current.next;
  }

  return false;
}

현재 노드가 이미 visited에 있다면 재방문이므로 true를 반환한다. null에 도달할 때까지 재방문이 없다면 순환이 없으므로 false를 반환한다.

이 풀이는 직관적이지만 방문한 모든 노드를 저장해야 한다. 노드가 n개라면 추가 공간이 O(n) 필요하다. 여기서 이 문제의 핵심 질문이 생긴다.

지나온 노드를 모두 기억하지 않고도, 계속 같은 구간을 돌고 있다는 사실을 알아낼 수 있을까?

같은 트랙 위의 두 포인터

한 번에 한 노드씩 이동하는 slow와 한 번에 두 노드씩 이동하는 fast를 같은 위치에서 출발시킨다.

slow = slow.next; // 한 칸 이동
fast = fast.next.next; // 두 칸 이동

순환이 없다면 더 빠른 fast가 먼저 리스트의 끝에 도달한다. fast 또는 fast.next가 null이면 리스트에는 순환이 없다.

순환이 있다면 상황이 달라진다. 두 포인터 모두 언젠가 순환 구간 안으로 들어가고, 그 뒤에는 어느 포인터도 null에 도달하지 않는다. fast는 매번 slow보다 한 노드만큼 더 이동하므로 원형 트랙에서 뒤를 따라잡듯 결국 slow와 같은 노드에 도달한다.

slow: 1칸씩 이동
fast: 2칸씩 이동

한 번 이동할 때마다 slow를 기준으로 한 fast의 상대 위치는 1칸씩 이동한다.

1 -> 2 : 1
2 -> 4 : 2
3 -> 6 : 3
...

이 방법을 Floyd의 순환 탐지 알고리즘, 또는 토끼와 거북이 알고리즘이라고 부른다.

왜 두 포인터는 반드시 만나는가

두 포인터가 순환 구간에 들어간 순간을 원형 트랙 위의 두 사람이라고 생각해 보자. 같은 방향으로 달리지만 slow는 한 번에 한 칸, fast는 한 번에 두 칸 이동한다.

어느 시점에 fast가 앞으로 3칸 더 가야 slow의 현재 위치에 도달할 수 있다고 하자. 다음 이동에서 fast는 두 칸 가지만 slow도 한 칸 앞으로 이동한다. 결국 두 포인터 사이에서 실제로 줄어든 간격은 한 칸이다.

fast에서 slow까지 남은 간격

3칸 → 2칸 → 1칸 → 0칸

두 포인터가 모두 계속 움직이더라도 fast는 매번 slow보다 정확히 한 칸을 더 간다. 따라서 fast가 한 바퀴를 돌며 따라오는 동안 둘 사이의 간격은 한 칸씩 줄어들고, 간격이 0이 되는 순간 같은 노드에 서게 된다.

fast가 두 칸씩 이동하므로 slow를 뛰어넘을 수 있을 것처럼 보일 수도 있다. 하지만 두 포인터를 함께 움직이는 관점에서는 상대 속도가 한 칸이다. 간격이 1칸 남은 상태에서 다음 이동을 해보면 slow는 한 칸, fast는 두 칸 이동하므로 둘은 정확히 같은 노드에 도착한다. 비교 시점을 건너뛰지 않는다.

순환 구간은 출구가 없는 원형이므로 fast가 따라잡기 전에 리스트가 끝나는 일도 없다. 직선 트랙이라면 빠른 포인터가 끝에 먼저 도착할 수 있지만, 원형 트랙에서는 간격을 계속 좁힐 수밖에 없다.

이 직관을 위치 관계로 표현하면 다음과 같다.

순환 구간의 노드 수를 k라고 하자. 두 포인터가 모두 순환 안에 있을 때, slow를 기준으로 본 fast의 상대 위치는 한 번의 반복마다 1만큼 변한다.

상대 위치: d, d + 1, d + 2, ... (mod k)

순환 안에서는 위치가 k개뿐이다. 따라서 상대 위치를 k로 나눈 나머지는 최대 k번 안에 반드시 0이 된다. 상대 위치가 0이라는 것은 두 포인터가 같은 노드를 가리킨다는 뜻이다.

중요한 점은 fast가 slow를 건너뛰어 영원히 만나지 못하는 일이 없다는 것이다. fast는 한 번에 두 칸, slow는 한 번에 한 칸 이동하므로 실제 상대 속도는 한 칸이다. 순환 구간에서 두 포인터 사이의 간격은 한 번에 한 칸씩 변하고, 결국 정확히 같은 위치가 된다.

포인터가 움직이는 과정

다음 리스트에서 D.next는 B를 가리킨다고 하자.

A → B → C → D -> B

두 포인터를 A에서 시작해 먼저 이동한 뒤 비교하면 다음과 같다.

반복	`slow`	`fast`	같은 노드인가?
1	`B`	`C`	아니오
2	`C`	`B`	아니오
3	`D`	`D`	예

세 번째 반복에서 두 포인터가 같은 D 노드를 가리키므로 순환이 존재한다.

여기서 비교해야 하는 것은 노드의 값이 아니라 노드 객체 자체가 같은지 여부다.

slow === fast;

서로 다른 두 노드가 같은 값을 가질 수 있기 때문에 slow.val === fast.val로 비교하면 순환이 없는 리스트도 순환이 있다고 잘못 판단할 수 있다.

[서로 다른 노드]
A(1) → B(1) → null

A와 B의 값은 모두 1이지만 같은 노드는 아니다.

TypeScript 풀이

class ListNode {
  val: number;
  next: ListNode | null;

  constructor(val = 0, next: ListNode | null = null) {
    this.val = val;
    this.next = next;
  }
}

function hasCycle(head: ListNode | null): boolean {
  let slow = head;
  let fast = head;

  while (fast !== null && fast.next !== null) {
    slow = slow?.next ?? null;
    fast = fast.next.next;

    if (slow === fast) {
      return true;
    }
  }

  return false;
}

fast는 한 번에 두 노드를 이동하므로 이동 전에 현재 노드와 다음 노드가 모두 존재하는지 확인해야 한다.

while (fast !== null && fast.next !== null)

이 조건을 만족하지 못했다는 것은 fast가 리스트의 끝에 도달했다는 뜻이다. 순환이 있다면 끝에 도달할 수 없으므로 반복문 밖에서는 false를 반환한다.

포인터 비교는 이동한 뒤에 수행한다. 두 포인터가 모두 head에서 출발하므로 이동 전에 비교하면 모든 입력에서 곧바로 같다고 판단하기 때문이다.

경계 조건도 같은 흐름으로 처리된다

빈 리스트에서는 fast가 처음부터 null이므로 반복문을 실행하지 않는다.
노드가 하나이고 next가 null이면 fast.next가 없으므로 반복문을 실행하지 않는다.
노드 하나가 자기 자신을 가리키면 한 번 이동한 뒤 slow와 fast가 모두 같은 노드를 가리킨다.
순환이 리스트의 중간에서 시작하더라도 두 포인터는 결국 순환 구간에 함께 들어가 만난다.

별도의 분기 없이 반복 조건과 포인터의 만남만으로 모든 경우를 처리할 수 있다.

복잡도

순환이 없으면 fast가 리스트 끝에 도달할 때까지 이동한다. 순환이 있으면 두 포인터가 순환 구간에 들어간 뒤, 순환 구간의 길이 이내에 만난다. 따라서 시간 복잡도는 O(n)이다.

입력 크기와 관계없이 두 개의 포인터만 사용하므로 추가 공간 복잡도는 O(1)이다. 방문 노드를 저장하는 Set 풀이와 비교하면 같은 선형 시간 복잡도를 유지하면서 추가 공간을 없앴다.

이 문제의 사고 전환

처음에는 “이 노드를 전에 방문했는가?”를 직접 기억하는 방식이 자연스럽다. Floyd 알고리즘은 질문을 바꾼다.

서로 다른 속도로 이동하는 두 포인터가 같은 노드에서 만나는가?

순환이 없다면 빠른 포인터가 끝에 도달하고, 순환이 있다면 두 포인터의 상대 속도 때문에 반드시 만난다. 즉, 과거의 모든 방문 기록을 저장하는 대신 현재 두 포인터의 관계만으로 순환을 판별한다.

이 아이디어는 연결 리스트에만 한정되지 않는다. 어떤 상태에서 다음 상태가 하나로 결정되는 구조라면, 상태 전이가 끝나는지 아니면 이전 상태로 되돌아가 반복되는지를 같은 방식으로 검사할 수 있다.

null을 찾는 대신 재방문을 찾아야 한다