콘텐츠로 이동

Floyd의 연결 리스트 사이클 탐지 알고리즘

시작점이 head로 표시되는 연결 리스트가 주어지며, 이 연결 리스트에는 사이클이 있을 수도 있고 없을 수도 있습니다. 예를 들면 다음과 같습니다.

여기서는 사이클의 시작점인 지점 C를 찾아야 합니다.

제안하는 알고리즘

이 알고리즘은 Floyd의 사이클 알고리즘 또는 토끼와 거북이(Tortoise And Hare) 알고리즘이라고 부릅니다. 사이클의 시작점을 알아내려면 먼저 사이클이 존재하는지부터 알아내야 합니다. 이 과정은 두 단계로 이루어집니다. 1. 사이클의 존재 여부를 알아냅니다. 2. 사이클의 시작점을 찾습니다.

1단계: 사이클의 존재 여부

  1. 두 포인터 $slow$와 $fast$를 준비합니다.
  2. 처음에는 두 포인터 모두 연결 리스트의 head를 가리킵니다.
  3. $slow$는 한 번에 한 칸씩 이동합니다.
  4. $fast$는 한 번에 두 칸씩 이동합니다. ($slow$ 포인터보다 두 배 빠른 속도입니다.)
  5. 둘 중 하나(또는 둘 다)가 null에 도달하기 전에 어느 시점에서든 두 포인터가 같은 노드를 가리키는지 확인합니다.
  6. 이동하는 도중 어느 시점에서든 두 포인터가 같은 노드를 가리키면, 연결 리스트에 실제로 사이클이 존재한다는 뜻입니다.
  7. null을 만나면 연결 리스트에 사이클이 없다는 뜻입니다.

이제 연결 리스트에 사이클이 있는지 알아냈으므로, 다음 단계에서는 사이클의 시작점, 즉 C를 찾아야 합니다.

2단계: 사이클의 시작점

  1. $slow$ 포인터를 연결 리스트의 head로 되돌립니다.
  2. 두 포인터를 모두 한 번에 한 칸씩 이동시킵니다.
  3. 두 포인터가 만나는 지점이 사이클의 시작점입니다.
// Presence of cycle
public boolean hasCycle(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;

    while(fast != null && fast.next != null){
        slow = slow.next;
        fast = fast.next.next;
        if(slow==fast){
            return true;
        }
    }

    return false;
}

// Assuming there is a cycle present and slow and fast are point to their meeting point
slow = head;
while(slow!=fast){
    slow = slow.next;
    fast = fast.next;
}

return slow; // the starting point of the cycle.

이 알고리즘이 동작하는 이유

1단계: 사이클의 존재 여부

포인터 $fast$는 $slow$보다 두 배 빠른 속도로 이동하므로, 어느 시점에서든 $fast$는 $slow$보다 두 배 먼 거리를 이동했다고 할 수 있습니다. 또한 두 포인터가 이동한 거리의 차이가 $1$씩 증가한다는 것도 추론할 수 있습니다. 

slow: 0 --> 1 --> 2 --> 3 --> 4 (distance covered)
fast: 0 --> 2 --> 4 --> 6 --> 8 (distance covered)
diff: 0 --> 1 --> 2 --> 3 --> 4 (difference between distance covered by both pointers)
$L$을 사이클의 길이라 하고, $a$를 느린 포인터가 사이클의 입구에 도달하는 데 필요한 이동 횟수라고 합시다. $k \cdot L \geq a$를 만족하는 양의 정수 $k$($k > 0$)가 존재합니다. 느린 포인터가 $k \cdot L$칸을 이동하고 빠른 포인터가 $2 \cdot k \cdot L$칸을 이동했을 때, 두 포인터는 모두 사이클 안에 있습니다. 이 시점에서 두 포인터 사이의 간격은 $k \cdot L$입니다. 사이클의 길이가 $L$로 유지되므로, 이는 두 포인터가 사이클 안의 같은 지점에 있다는 것을 의미하며, 결과적으로 두 포인터는 만나게 됩니다.

2단계: 사이클의 시작점

두 포인터가 사이클 안에서 만나는 지점까지 각각 이동한 거리를 계산해 봅시다.

$slowDist = a + xL + b$ , $x\ge0$

$fastDist = a + yL + b$ , $y\ge0$

  • $slowDist$는 느린 포인터가 이동한 총 거리입니다.
  • $fastDist$는 빠른 포인터가 이동한 총 거리입니다.
  • $a$는 두 포인터가 사이클에 들어가기 위해 이동해야 하는 걸음 수입니다.
  • $b$는 C와 G 사이의 거리, 즉 사이클의 시작점과 두 포인터가 만나는 지점 사이의 거리입니다.
  • $x$는 느린 포인터가 C를 시작점이자 끝점으로 하여 사이클 안을 돈 횟수입니다.
  • $y$는 빠른 포인터가 C를 시작점이자 끝점으로 하여 사이클 안을 돈 횟수입니다.

$fastDist = 2 \cdot (slowDist)$

$a + yL + b = 2(a + xL + b)$

식을 정리하면 다음을 얻습니다:

$a=(y-2x)L-b$

여기서 $y-2x$는 정수입니다

이는 기본적으로 $a$ 걸음이 사이클에서 완전한 루프를 몇 번 돈 다음 $b$ 걸음 뒤로 가는 것과 같다는 뜻입니다. 빠른 포인터는 이미 사이클 입구보다 $b$걸음 앞에 있으므로, 빠른 포인터가 $a$걸음을 더 이동하면 사이클의 입구에 도착하게 됩니다. 그리고 느린 포인터는 연결 리스트의 시작점에서 출발하게 했으므로, $a$걸음 뒤에는 느린 포인터도 사이클 입구에 도착하게 됩니다. 따라서 두 포인터가 모두 $a$걸음을 이동하면 둘 다 사이클의 입구에서 만나게 됩니다.

문제: