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

연결된 목록에서 효율적인 루프 감지

연결된 목록에서 루프를 감지하는 것은 데이터 구조와 알고리즘에 대한 정교한 이해가 필요한 고전적인 면접 질문입니다. 우리는 Floyd의 주기 찾기 알고리즘을 사용하여 이 문제에 대한 세심한 해결책을 제시합니다.

Floyd의 알고리즘은 한 번에 한 단계씩 진행하는 기준과 두 단계씩 진행하는 기준을 사용합니다. 이러한 차등 속도는 목록에 루프가 있는 경우 결국 두 참조가 만나게 됩니다.

다음은 알고리즘의 단계별 분석입니다.

1. 두 참조를 초기화합니다. 느린 속도와 빠른 속도를 목록의 첫 번째 노드로 참조합니다.
2. 각 단계에서 한 노드씩 느리게 진행하고 두 노드씩 빠르게 진행합니다.
3. 느림 또는 빠름 중 하나가 null이 되는지 확인하세요. 이는 루프가 없음을 나타냅니다.
4. 느림과 빠름이 같은지 확인하세요. 그렇다면 루프가 존재하는 것입니다.

다음 Java 함수는 Floyd의 알고리즘을 구현합니다.

<code class="java">public static boolean hasLoop(Node first) {

    if (first == null) // List does not exist, no loop
        return false;

    Node slow, fast; // Create two references

    slow = fast = first; // Point both to the start of the list

    while (true) {

        slow = slow.next; // 1 hop

        if (fast.next != null)
            fast = fast.next.next; // 2 hops
        else
            return false; // Next node null -> no loop

        if (slow == null || fast == null) // If either hits null, no loop
            return false;

        if (slow == fast) // If the two ever meet, we have a loop
            return true;
    }
}</code>

이 알고리즘은 두 개의 참조만 사용하므로 일정한 공간 복잡도를 갖습니다. O(n)의 합리적인 시간 복잡도. 여기서 n은 목록의 노드 수입니다.

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