Floyd의 알고리즘은 연결 목록의 루프를 어떻게 감지합니까?

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

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

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

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

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

<code class="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.
        }
    }
}</code>

이 알고리즘은 O(1) 공간 복잡도를 가지며 O(n) 시간에 실행되므로 메모리 효율적이면서 합리적인 시간 소모가 됩니다.

위 내용은 Floyd의 알고리즘은 연결 목록의 루프를 어떻게 감지합니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!