Floyd 알고리즘을 사용하여 연결된 목록에서 루프 감지

주어진 연결된 목록에 루프가 포함되어 있는지 확인하는 것은 Java 프로그래밍에서 어려운 작업일 수 있습니다. 목록의 마지막 노드가 널 참조가 아닌 이전 노드를 참조할 때 루프가 발생합니다.

루프를 효율적으로 감지하기 위해 개발자는 종종 거북이와 토끼 알고리즘이라고도 알려진 플로이드의 주기 찾기 알고리즘을 사용합니다. . 이 알고리즘은 서로 다른 속도로 목록을 탐색하는 느린 참조와 빠른 참조 두 개를 사용합니다.

예를 들어 느린 참조는 노드 1개만큼 진행되는 반면 빠른 참조는 노드 2개만큼 진행됩니다. 연결된 목록에 루프가 포함되어 있으면 이러한 참조는 결국 만나게 됩니다. 반면, 루프가 없으면 느리거나 빠른 참조(또는 후속 참조)는 다른 참조가 목록 끝에 도달하기 전에 null이 됩니다.

여기에 Floyd 알고리즘의 Java 구현이 있습니다. :

boolean hasLoop(Node first) {
    if (first == null) {
        return false; // List does not exist, so no loop
    }

    Node slow, fast; // Create two references.
    slow = fast = first; // Make both refer to the start of the list.

    while (true) {
        slow = slow.next; // One hop.

        if (fast.next != null) {
            fast = fast.next.next; // Two hops.
        } else {
            return false; // No loop.
        }

        if (slow == null || fast == null) {
            return false; // No loop.
        }

        if (slow == fast) {
            return true; // Loop detected.
        }
    }
}

이 알고리즘은 O(1) 공간 복잡성을 취하고 O(n) 시간에 실행되므로 메모리 효율적이면서 합리적인 시간 소모적입니다.