Algoritma untuk menentukan apakah loop ada dalam daftar tertaut

Jadi saya baru-baru ini menemukan algoritma untuk menentukan apakah suatu siklus ada dalam daftar tertaut. Kode-kodenya adalah sebagai berikut:

public boolean hasCycle(ListNode head) {
    if (head == null) {
        return false;
    }
    ListNode fast = head;
    ListNode slow = head;
    while (fast != null) {
        if (fast.next == null) {
            return false;
        }
        if (fast.next == slow) {
            return true;
        }
        fast = fast.next.next;
        slow = slow.next;
    }
    return false;
}

Saat mencoba membuktikan kebenaran algoritma ini, saya mendapat ide: Misalkan keliling siklus adalah "a", waktu yang berlalu sebelum dua penunjuk bertemu adalah "t". Karena kecepatan simpul "cepat" bergerak dua kali lebih cepat dari simpul "lambat", kita dapat memperoleh hubungan matematisnya:

2t mod a = t mod a

Sekarang "a" adalah konstanta yang mewakili keliling, dan "t" bisa jadi 1,2,3.... Lalu, bagaimana cara membuktikan bahwa berapa pun nilai "a", kita selalu dapat menemukan "t" seperti itu apakah persamaan di atas dapat diselesaikan?


loops algorithm linked-list
person Zhengyang Fang    schedule 06.10.2016    source sumber
comment
stackoverflow.com/q/2936213/1835769   -  person displayName    schedule 06.10.2016
comment
apakah persamaan tersebut benar jika siklus tidak dimulai pada simpul pertama? misal: 1-›2, 2-›3, 3-›4, 4-›5, 5-›3, siklus = {3,4,5,3}   -  person shole    schedule 06.10.2016
comment
Setiap t = 0 mod a memecahkan 2t = t mod a. Anda juga memerlukan t >= s, yang memerlukan s langkah untuk memasuki siklus.   -  person Matt Timmermans    schedule 06.10.2016
comment
@MattTimmermans ummm...Saya pikir mungkin sama setelah saya berpikir sejenak: 2t -s = t-s (a) jadi 2t = t (a), tapi tidak yakin   -  person shole    schedule 06.10.2016
comment
@shole, Anda memerlukan kedua kondisi tersebut. Jika diperlukan 13 langkah untuk memasuki siklus yang panjangnya 10, maka penunjuknya akan bertemu di t=20 dan t=30, tetapi tidak bertemu di t=10   -  person Matt Timmermans    schedule 06.10.2016
comment
@MattTimmermans Yup Anda benar   -  person shole    schedule 06.10.2016

Jawaban (2)


arrow_upward
0
arrow_downward

Anda berada di jalur yang benar! Petunjuk: apa yang terjadi pada rumus Anda setelah perulangan a?

person Aasmund Eldhuset    schedule 06.10.2016

arrow_upward
0
arrow_downward

Dengan asumsi kedua penunjuk dimulai pada titik yang sama dalam siklus (dan ini tidak dihitung sebagai pertemuan)

2t = t (a)

=> 2t - t = 0 (a)

=> t = 0 (a)

Artinya pada t = a*k, kedua penunjuk akan bertemu di titik awal setelah waktu yang berlalu merupakan kelipatan panjang siklus.

Hal ini berlaku untuk semua a >= 2, karena ketika waktu sama dengan k*a untuk semua k>1, penunjuk lambat berjalan tepat sepanjang k siklus, sedangkan penunjuk cepat berjalan dua kali lebih cepat, sehingga panjangnya berjalan 2k siklus, namun keduanya tetap bertemu di titik yang sama yaitu titik awal.

person shole    schedule 06.10.2016
comment
Saya tersesat pada langkah kedua Anda : ( bagaimana cara mendapatkan 2t - t = 0 (a) dari 2t = t (a)? - person Zhengyang Fang; 10.10.2016
comment
Hanya minus t%a di kedua sisi? - person shole; 11.10.2016