Kesan kitaran dalam senarai terpaut

Satu lagi algoritma senarai terpaut.

Kesan kitaran dalam senarai terpaut.

Ini sebenarnya tidak begitu teruk. Terdapat sekurang-kurangnya 3 cara berbeza untuk melakukannya pada masa O(n).

Cara paling mudah memerlukan pengubahsuaian nod senarai terpaut untuk memasukkan bendera yang menandakan jika nod telah dilawati. Semasa senarai dilalui, jika kita menemui nod yang telah dilawati maka terdapat kitaran.

Teknik lain menggunakan peta cincang yang mengandungi nod yang dilawati atau rujukan kepadanya. Apabila senarai dilalui nod, atau rujukannya, dimasukkan ke dalam cincang. Jika kita menemui nod yang sudah diwakili dalam peta cincang, maka kitaran wujud. Walaupun teknik ini hanya memerlukan satu traversal, ia memerlukan lebih banyak memori kerana peta cincang.

Untuk siaran ini, saya akan menggunakan algoritma Floyd untuk mengesan kitaran. Ia agak mudah.

func DetectCycle[T any](ll *LinkedList[T]) bool {
    slow := ll.Head
    fast := ll.Head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        if fast == slow {
            return true
        }
    }
    return false
}

Teknik ini menggunakan 2 penunjuk ke dalam senarai. Semasa senarai dilalui, satu penunjuk menggerakkan satu nod pada satu masa dan satu lagi menggerakkan dua nod pada satu masa. Jika 2 pointer pernah bertemu, satu kitaran wujud.

Mengapa ini berfungsi? Apabila senarai dilalui, jarak antara dua penunjuk bertambah. Jika ada kitaran, penunjuk pantas akan 'lap' yang perlahan.

Adakah terdapat pelaksanaan yang lebih cekap? Adakah sebarang syarat sempadan hilang? Beritahu saya dalam ulasan.

Terima kasih!

Kod untuk siaran ini dan semua siaran dalam siri ini boleh didapati di sini

Atas ialah kandungan terperinci Kesan kitaran dalam senarai terpaut. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!