CTCI | Loop

Linked List에 있는 Loop을 찾아라

Linked List에 Cycle이 있을 수 있다. 이런 경우, 제일 첫번째 노드를 찾으라는 문제이다. 이 문제는 내가 가장 좋아하는 문제중 하나이다. 플로이드의 거북이와 토끼 알고리즘을 이용해서 풀 수 있는데, 이 알고리즘은 마치 이야기 속에서 튀어나온 듯한, 연결 리스트에서 사이클을 찾는 데에 사용되는 기발한 방법이다. 이 알고리즘은 두 주인공, 느린 거북이와 빠른 토끼를 등장시킨다. 이들은 같은 출발점, 즉 리스트의 헤드에서 여정을 시작한다.

이야기는 이렇다: 거북이는 한 번에 한 걸음씩 꾸준히 앞으로 나아간다. 반면, 토끼는 매우 빠르기 때문에, 두 걸음씩 뛴다. 만약 리스트에 사이클이 존재하지 않는다면, 토끼는 리스트의 끝에 도달하여 멈춘다. 하지만 사이클이 있다면, 이야기는 훨씬 더 흥미로워진다.

사이클이 존재하는 순간, 토끼와 거북이는 결국 같은 위치에 도달하게 된다. 왜냐하면 토끼가 앞서 나가도 결국 사이클 내를 돌면서 거북이를 만나게 되기 때문이다. 이 순간이 바로 토끼와 거북이가 만나는 마법의 순간이다.

토끼와 거북이가 만났을 때, 거북이는 그 자리에 머무르고, 토끼는 다시 출발선으로 돌아간다. 하지만 이번에는 토끼도 거북이처럼 한 걸음씩만 이동한다. 이들이 다시 만나는 지점, 바로 그곳이 사이클의 시작점이 된다. 이처럼, 거북이와 토끼는 리스트 내의 숨겨진 사이클을 밝혀내는 데 결정적인 역할을 한다.

플로이드의 거북이와 토끼 알고리즘은 연결 리스트 내에서 사이클을 간단하게 찾을 수 있는 강력한 방법을 제공한다. 이 알고리즘은 그 간단함에도 불구하고 놀라운 효율성을 자랑하며, 사이클의 존재와 시작점을 정확히 찾아낼 수 있다. 이야기처럼 시작하여 수학적 원리로 끝나는 이 방법은, 알고리즘 세계에서의 창의성과 지능의 멋진 예시를 보여준다. 자, 그럼 이것을 코드로 나타내보자.

 

Node findCycle(Node head) {
    if (head == null || head.next == null) {
        return null;
    }
    Node slow = head, fast = head;

    do {
    
    	// 사이클이 없다면, fast 또는 fast.next는 null이다.
        if (fast == null || fast.next == null) {
            return null;
        }
        
        // slow는 한걸음, fast는 두걸음 보낸다.
        // 토끼와 거북이이다.
        slow = slow.next;
        fast = fast.next.next;
    } while (slow != fast);

    // 사이클 시작점 찾기
    // slow를 다시 head로 보낸다.
    slow = head;
    
    // slow와 fast가 만날때까지 loop을 돌린다.
    while (slow != fast) {
    
    	// 이제 한 번에 한 노드씩, 토끼와 거북이를 같은 속도로 움직인다.
        slow = slow.next;
        fast = fast.next;
    }

    return slow; // 사이클의 시작 노드를 리턴한다.
}

 

시간복잡도: 전체 알고리즘의 시간 복잡도는 O(N) + O(N) = O(N)이다. 즉, 리스트의 길이에 비례하는 시간이 소요된다.

공간복잡도: 알고리즘은 추가적인 데이터 구조를 사용하지 않는다. 모든 연산은 slow와 fast라는 두 개의 포인터만을 이용해 이루어진다. 이는 추가적인 공간을 필요로 하지 않으므로, 알고리즘의 공간 복잡도는 O(1)이다. 즉, 고정된 크기의 공간만을 사용한다.