Bagaimanakah Algoritma Floyd Mengesan Gelung dalam Senarai Terpaut?

Mengesan Gelung dalam Senarai Terpaut Menggunakan Algoritma Floyd

Menentukan sama ada senarai terpaut yang diberikan mengandungi gelung boleh menjadi tugas yang mencabar dalam pengaturcaraan Java. Gelung berlaku apabila nod akhir dalam senarai merujuk kepada nod sebelumnya dan bukannya mempunyai rujukan nol.

Untuk mengesan gelung dengan cekap, pembangun sering menggunakan algoritma pencarian kitaran Floyd, yang juga dikenali sebagai algoritma kura-kura dan arnab . Algoritma ini menggunakan dua rujukan, yang perlahan dan yang cepat, yang melintasi senarai pada kelajuan yang berbeza.

Sebagai contoh, rujukan yang perlahan mendahului satu nod manakala rujukan yang pantas memajukan dua nod. Jika senarai terpaut mengandungi gelung, rujukan ini akhirnya akan bertemu. Sebaliknya, jika tiada gelung, sama ada rujukan perlahan atau cepat (atau rujukan seterusnya) akan menjadi batal sebelum yang lain sampai ke penghujung senarai.

Berikut ialah pelaksanaan Java bagi algoritma Floyd :

<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>

Algoritma ini mengambil O(1) kerumitan ruang dan berjalan dalam masa O(n), menjadikannya cekap ingatan dan memakan masa yang munasabah.

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