Bagaimanakah Algoritma Pencarian Kitaran Floyd Mengesan Gelung dalam Senarai Terpaut?

Pengesanan Gelung Cekap dalam Senarai Terpaut

Mengesan gelung dalam senarai terpaut ialah soalan temu bual klasik yang memerlukan pemahaman yang sofistikated tentang struktur data dan algoritma. Kami membentangkan penyelesaian yang teliti untuk masalah ini menggunakan algoritma pencarian kitaran Floyd.

Algoritma Floyd menggunakan dua rujukan, satu memajukan satu langkah pada satu masa dan satu lagi memajukan dua langkah pada satu masa. Kelajuan pembezaan ini memastikan bahawa jika terdapat gelung dalam senarai, kedua-dua rujukan itu akhirnya akan bertemu.

Berikut ialah pecahan langkah demi langkah bagi algoritma:

1. Mulakan dua rujukan, perlahan dan cepat, ke nod pertama dalam senarai.
2. Maju perlahan dengan satu nod dan pantas dengan dua nod pada setiap langkah.
3. Semak sama ada lambat atau cepat menjadi batal. Ini menunjukkan ketiadaan gelung.
4. Semak sama ada lambat dan cepat adalah sama. Jika ya, gelung wujud.

Fungsi Java berikut melaksanakan algoritma 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>

Algoritma ini mempunyai kerumitan ruang yang berterusan, kerana ia hanya menggunakan dua rujukan dan kerumitan masa yang munasabah bagi O(n), dengan n ialah bilangan nod dalam senarai.

Atas ialah kandungan terperinci Bagaimanakah Algoritma Pencarian Kitaran Floyd Mengesan Gelung dalam Senarai Terpaut?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!