Jelaskan bagaimana cara kerja simpul start siklus dalam daftar yang terhubung siklus berfungsi?

162

Saya mengerti bahwa pertemuan Tortoise dan Hare menyimpulkan keberadaan loop, tetapi bagaimana cara memindahkan kura-kura ke awal daftar tertaut sambil menjaga kelinci di tempat pertemuan, diikuti dengan memindahkan kedua langkah sekaligus membuat mereka bertemu di titik awal siklus?

Pemrogram yang bergairah
sumber
Penjelasan lain: marcin-chwedczuk.github.io/…
csharpfolk
Orang tidak peduli untuk melihat lebih dari dua jawaban pertama untuk pertanyaan ini. Jawaban ketiga cukup bagus.
displayName

Jawaban:

80

Ini adalah algoritma Floyd untuk deteksi siklus . Anda bertanya tentang fase kedua dari algoritma - setelah Anda menemukan simpul yang merupakan bagian dari siklus, bagaimana orang menemukan awal siklus?

Pada bagian pertama dari algoritma Floyd, kelinci menggerakkan dua langkah untuk setiap langkah kura-kura. Jika kura-kura dan kelinci pernah bertemu, ada siklus, dan titik pertemuan adalah bagian dari siklus, tetapi belum tentu simpul pertama dalam siklus.

Ketika kura-kura dan kelinci bertemu, kami telah menemukan i terkecil (jumlah langkah yang diambil oleh kura-kura) sehingga X i = X 2i . Biarkan mu mewakili jumlah langkah untuk mulai dari X 0 ke awal siklus, dan biarkan lambda mewakili panjang siklus. Kemudian i = mu + a lambda, dan 2i = mu + b lambda, di mana a dan b adalah bilangan bulat yang menunjukkan berapa kali kura-kura dan kelinci mengelilingi siklus. Mengurangi persamaan pertama dari yang kedua memberi i = (ba) * lambda, jadi saya adalah kelipatan integer dari lambda. Karena itu, X i + mu = X mu . X i mewakili titik pertemuan kura-kura dan kelinci. Jika Anda memindahkan kura-kura kembali ke simpul awal X0 , dan biarkan kura-kura dan kelinci melanjutkan dengan kecepatan yang sama, setelah langkah-langkah tambahan mu kura-kura akan mencapai X mu , dan kelinci akan mencapai X i + mu = X mu , sehingga titik pertemuan kedua menunjukkan awal dari siklus.

Jim Lewis
sumber
1
@ Jim lewis Titik pertemuan tidak akan menjadi titik awal tentu saja, tetapi seperti yang saya katakan, menggeser salah satu dari dua ke awal daftar tertaut dan memindahkan keduanya dengan kecepatan yang sama akan membuat mereka bertemu di titik awal siklus.
Pemrogram yang bergairah
6
@ Jim Lewis Akan lebih baik jika Anda bisa menjelaskan tentang bagaimana memiliki saya sebagai kelipatan dari hasil panjang loop ke mu sebagai jarak antara titik pertemuan pertama dan awal loop.
Pemrogram yang bergairah
7
@Passionate: Ambil langkah mu dari titik awal untuk menuju X_mu, awal siklus (menurut definisi mu). Kemudian jika Anda mengambil lebih banyak langkah, di mana saya adalah kelipatan dari panjang siklus, Anda berakhir kembali di awal siklus: X_mu + i= X_mu. Tetapi penambahan itu bersifat komutatif, jadi ini sama dengan mengambil langkah-langkah untuk memulai dari awal sampai titik pertemuan pertama X_i, lalu mengambil langkah-langkah tambahan untuk kembali ke X_mu, awal siklus.
Jim Lewis
2
@ankur: Titik pertemuan adalah X_i, dan kami telah menunjukkan (paragraf ketiga dalam jawaban saya) bahwa saya harus kelipatan dari panjang loop. Setelah langkah tambahan Anda melewati titik pertemuan, Anda sekarang berada di X_ (i + mu). Tetapi kami telah menunjukkan bahwa X_ (i + mu) = X_ (mu + i) = X_mu, karena properti khusus ini dari saya, jadi langkah mu melewati titik pertemuan harus membawa Anda ke X_mu, awal siklus. Pada dasarnya modular hitung, ditambah sifat komutatif dari penambahan.
Jim Lewis
28
Saya pikir ada masalah kecil di buktimu. Karena titik pertemuan iberada di beberapa titik siklus, saya pikir persamaannya harus i = mu + k + a*lambdadan 2i = mu + k + b*lambda, di mana kjumlah langkah dari siklus mulai ke titik pertemuan. Mengurangi kedua persamaan memberikan hasil yang sama.
Ivan Z. Siu
336

Biarkan saya mencoba untuk mengklarifikasi algoritma deteksi siklus yang disediakan di http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare dengan kata-kata saya sendiri.

gambar

Bagaimana itu bekerja

Mari kita memiliki kura-kura dan kelinci (nama pointer) yang menunjuk ke awal daftar dengan siklus, seperti pada diagram di atas.

Mari berhipotesis bahwa jika kita memindahkan kura-kura 1 langkah sekaligus, dan membagi 2 langkah sekaligus, mereka akhirnya akan bertemu pada suatu titik. Mari kita tunjukkan bahwa pertama-tama hipotesis ini benar.

Angka tersebut menggambarkan daftar dengan siklus. Siklus memiliki panjang ndan kami awalnya beberapa mlangkah menjauh dari siklus. Juga katakanlah bahwa titik pertemuan adalah beberapa klangkah menjauh dari siklus awal dan kura-kura dan kelinci bertemu ketika kura-kura telah mengambil ilangkah-langkah total. (Kelinci akan mengambil 2ilangkah total saat itu.)

2 kondisi berikut harus berlaku:

1) i = m + p * n + k

2) 2i = m + q * n + k

Yang pertama mengatakan bahwa kura-kura bergerak ilangkah-langkah dan dalam ilangkah - langkah ini pertama kali sampai ke siklus. Kemudian ia melewati waktu siklus puntuk beberapa angka positif p. Akhirnya melewati lebih kbanyak node sampai bertemu kelinci.

Hal serupa juga berlaku untuk kelinci. Ini bergerak 2ilangkah-langkah dan langkah- 2ilangkah ini pertama kali sampai ke siklus. Kemudian ia melewati waktu siklus quntuk beberapa angka positif q. Akhirnya melewati lebih kbanyak node sampai bertemu kura-kura.

Saat kelinci berjalan dengan dua kali lipat kecepatan kura-kura, dan waktu konstan untuk keduanya ketika mereka mencapai titik pertemuan.

Jadi dengan menggunakan hubungan kecepatan, waktu dan jarak yang sederhana,

2 ( m + p * n + k ) = m + q * n + k

=> 2m + 2pn + 2k = m + nq + k 

=>  m + k = ( q - 2p ) n

Di antara m, n, k, p, q, dua yang pertama adalah properti dari daftar yang diberikan. Jika kita dapat menunjukkan bahwa setidaknya ada satu set nilai untuk k, q, p yang membuat persamaan ini benar, kita menunjukkan bahwa hipotesisnya benar.

Satu set solusi tersebut adalah sebagai berikut:

p = 0

q = m

k = m n - m

Kami dapat memverifikasi bahwa nilai-nilai ini berfungsi sebagai berikut:

m + k = ( q - 2p ) n  

=> m + mn - m = ( m - 2*0) n

=> mn = mn.

Untuk set ini, iadalah

i = m + p n + k

=> m + 0 * n + mn - m = mn.

Tentu saja, Anda harus melihat bahwa ini belum tentu yang terkecil yang saya bisa. Dengan kata lain, kura-kura dan kelinci mungkin sudah pernah bertemu sebelumnya. Namun, karena kami menunjukkan bahwa mereka bertemu di beberapa titik setidaknya sekali kita dapat mengatakan bahwa hipotesis itu benar. Jadi mereka harus bertemu jika kita memindahkan salah satu dari mereka 1 langkah, dan yang lainnya 2 langkah sekaligus.

Sekarang kita bisa menuju ke bagian kedua dari algoritma yang adalah bagaimana menemukan awal siklus.

Awal Siklus

Setelah kura-kura dan kelinci bertemu, mari kita meletakkan kura-kura kembali ke awal daftar dan simpan kelinci di tempat mereka bertemu (yang berjarak beberapa langkah dari siklus awal).

Hipotesisnya adalah jika kita membiarkan mereka bergerak dengan kecepatan yang sama (1 langkah untuk keduanya), pertama kali mereka bertemu lagi adalah siklusnya.

Mari kita buktikan hipotesis ini.

Pertama-tama mari kita asumsikan beberapa oracle memberi tahu kita apa itu m.

Kemudian, jika kita membiarkan mereka bergerak m + k langkah, kura-kura harus tiba pada titik yang mereka temui semula (k langkah menjauh dari siklus awal - lihat pada gambar).

Sebelumnya kami menunjukkan itu m + k = (q - 2p) n.

Karena langkah m + k adalah kelipatan dari panjang siklus n, kelinci, pada saat yang bersamaan, akan melewati siklus (q-2p) kali dan akan kembali ke titik yang sama (k langkah menjauh dari awal siklus).

Sekarang, alih-alih membiarkan mereka bergerak langkah m + k, jika kita membiarkan mereka bergerak hanya langkah m, kura-kura akan tiba di awal siklus. Kelinci akan menjadi k langkah-langkah pendek menyelesaikan rotasi (q-2p). Karena itu dimulai k langkah di depan siklus awal, kelinci harus tiba di siklus awal.

Akibatnya, ini menjelaskan bahwa mereka harus bertemu di siklus dimulai setelah beberapa langkah untuk pertama kalinya (sangat pertama karena kura-kura baru saja tiba di siklus setelah langkah m dan tidak pernah bisa melihat kelinci yang sudah ada di siklus).

Sekarang kita tahu bahwa jumlah langkah yang kita butuhkan untuk memindahkannya sampai bertemu ternyata menjadi jarak dari awal daftar ke awal siklus, m. Tentu saja, algoritma tidak perlu tahu apa itu m. Itu hanya akan memindahkan kedua kura-kura dan berbagi satu langkah pada satu waktu sampai mereka bertemu. Titik pertemuan harus menjadi awal siklus dan jumlah langkah harus jarak (m) ke awal siklus. Dengan asumsi kita tahu panjang daftar, kita juga bisa, menghitung panjang siklus pengurangan m dari panjang daftar.

CEGRD
sumber
1
Saya tidak berpikir begitu benar bahwa ketika mereka bertemu yang satu titik awal lihat komentar di bawah ini: stackoverflow.com/a/19209858/1744146 <br> Tolong beritahu saya Jika saya salah
MRA
Bagian pertama dari penjelasan tidak cacat. Tetapi bagian kedua memiliki kelemahan sejauh yang saya tahu. Anda berasumsi bahwa "beberapa kata oracle", tetapi jika m diketahui, Anda sudah memiliki awal siklus. Bagaimana Anda bisa mengasumsikan jawabannya ketika Anda tidak pernah tahu di mana awal siklusnya ?? Tolong beritahu saya.
Gopichand
1
@ Gopichand Baca para terakhir lagi ... Anda hanya berasumsi bahwa ada beberapa m (jika sudah terbukti ada siklus) .. tetapi Anda tidak tahu nilai m
Srinath
2
Sekarang ini penjelasan yang sangat fantastis. Ini mungkin penjelasan terbaik saat ini di seluruh internet.
Arlene Batada
2
Persamaan Anda m + k = (q - 2p) ndapat lebih disederhanakan menjadi m + k = q*n. Ini karena jumlah loop yang diambil kura-kura akan selalu nol karena kelinci tidak pernah bisa menyalip kura-kura tanpa memenuhi itu. Pikirkan tentang itu.
Arpit Jain
124

Rujuk gambar ini:

masukkan deskripsi gambar di sini

Jarak yang ditempuh oleh slowPointer sebelum pertemuan = x + y

Jarak yang ditempuh oleh fastPointer sebelum pertemuan = (x + y + z) + y = x + 2y + z

Karena fastPointer bergerak dengan dua kali lipat kecepatan slowPointer, dan waktu adalah konstan untuk keduanya ketika mencapai titik pertemuan.

Jadi dengan menggunakan hubungan kecepatan, waktu dan jarak yang sederhana 2 (x + y) = x + 2y + z => x + 2y + z = 2x + 2y => x = z

Oleh karena itu dengan menggerakkan slowPointer untuk memulai daftar tertaut, dan membuat slowPointer dan fastPointer untuk memindahkan satu node pada satu waktu, keduanya memiliki jarak yang sama untuk dibahas .

Mereka akan mencapai pada titik di mana loop dimulai pada daftar yang ditautkan.

Atul Yadav
sumber
10
Ini tidak memperhitungkan kasus fastPointer yang melakukan perjalanan siklus n kali sebelum slowPointer memasuki siklus. Gunakan l untuk menunjukkan panjang siklus. Jarak yang ditempuh oleh fastPointer sebelum pertemuan = (x + y + z) + y = x + 2y + nl + z. Dan relasi yang dihasilkan akan x = nl + z.
Jingguo Yao
@JingguoYao: Ini penjelasan untuk kasus itu.
displayName
2
diagram ini terlalu sederhana. pointer cepat dapat bergerak berkali-kali melalui siklus sebelum pointer lambat mencapainya.
Warren MacEvoy
70

Jawaban Old Monk yang sederhana dan kurang diselidiki menjelaskan menemukan siklus ketika pelari cepat hanya menyelesaikan satu siklus penuh. Dalam jawaban ini saya menjelaskan kasus ketika pelari cepat telah menjalankan loop beberapa kali sebelum pelari lambat memasuki loop.


Menggunakan gambar yang sama:masukkan deskripsi gambar di sini

Katakanlah pelari cepat telah menjalankan loop m kali sebelum bertemu lambat dan cepat. Ini berarti:

  • Jarak dijalankan dengan lambat: x + y
  • Jarak dijalankan dengan cepat: x + m (y + z) + y yaitu ekstra y tempat mereka bertemu

Karena berlari cepat dengan kecepatan dua kali lipat lambat, dan bahwa mereka telah berlari untuk waktu yang sama, itu menyiratkan bahwa jika kita menggandakan jarak berlari dengan lambat, kita mendapatkan jarak berlari dengan cepat. Jadi,

  • 2 (x + y) = x + m (y + z) + y

Memecahkan untuk x memberi,

x = (m - 1) (y + z) + z

Dalam skenario nyata itu berarti, x = (m - 1) loop lengkap berjalan + jarak ekstra z .

Oleh karena itu, jika kita meletakkan satu pointer di awal daftar dan meninggalkan yang lain di titik pertemuan, kemudian memindahkannya dengan kecepatan yang sama akan menghasilkan pointer loop menyelesaikan m - 1 putaran dan kemudian bertemu dengan lainnya arahkan tepat di awal loop.

nama tampilan
sumber
7
Satu keraguan .. bagaimana dijamin lambat dan cepat akan bertemu sebelum lambat mengambil lebih dari satu siklus?
siraj
4
@siraj: Lambat tidak akan berjalan dalam siklus, cepat karena berjalan lebih cepat dari lambat dan akan memasuki loop sebelumnya. Dan dijamin mereka akan bertemu. Jika lambat di j + 1 dan cepat di j, mereka sekarang akan bertemu di j + 2. Dan jika lambat di j dan 1 di j + 1, itu berarti bahwa mereka sudah bertemu di j - 1.
displayName
4
matematika masih bekerja jika lambat berkeliling loop: x + (y + z) m + y = 2 (x + (y + z) n + y), di mana n adalah # kali di sekitar loop untuk lambat sebelum mereka bertemu. Ini memecahkan ke (m-2n-1) (y + z) + z = x. Yang berarti mulai pada titik pertemuan, berkeliling (m-2n-1) kali, Anda kembali pada titik pertemuan, lalu pergi z, Anda berada di awal lingkaran. Dan untuk melakukan ini sama dengan memulai pada node kepala dan pergi x node.
mayas_mom
1
@mayas_mom: Matematika mungkin berhasil tetapi lambat tidak akan pernah bisa berputar. Itu akan selalu tertangkap baik di awal atau di suatu tempat di tengah jalan.
displayName
4
x = (m - 1) (y + z) + z ini dapat digeneralisasi karena panjang loop adalah y + z dan karena hanya memperhatikan posisi. Jadi x = ((m - 1) (y + z))% (y + z)) + z Yang secara efektif x = z;
anshul garg
10

Ini sangat sangat sederhana. Anda dapat berpikir dalam hal kecepatan relatif. Jika kelinci bergerak dua node dan kura-kura bergerak satu simpul, relatif terhadap kura-kura kelinci bergerak satu simpul (asumsikan kura-kura saat istirahat). Jadi, jika kita memindahkan satu simpul dalam daftar tertaut melingkar, kita yakin akan bertemu lagi di titik itu.

Setelah menemukan titik yang terhubung di dalam daftar tertaut melingkar, sekarang masalahnya dikurangi menjadi menemukan titik persimpangan dua masalah daftar tertaut.

murali krish
sumber
8

Gambar 1

Pada saat tabrakan pertama, kura-kura memindahkan langkah m + k seperti yang ditunjukkan di atas. Kelinci bergerak dua kali lebih cepat dari kura-kura, artinya kelinci bergerak 2 (m + k) langkah. Dari fakta-fakta sederhana ini kita dapat memperoleh grafik berikut.

Gambar 1

Pada titik ini, kami memindahkan kura-kura kembali ke awal dan menyatakan bahwa kelinci dan kura-kura harus bergerak selangkah demi selangkah. Menurut definisi, setelah langkah m , kura-kura akan berada di awal siklus. Di mana hare akan berada?

Kelinci juga akan berada di awal siklus. Hal ini jelas dari grafik kedua: Ketika kura-kura dipindahkan kembali ke awal, kelinci adalah k langkah ke siklus terakhir. Setelah langkah m , kelinci akan menyelesaikan siklus lain dan bertabrakan dengan kura-kura.

skedastik
sumber
@ WarrenMacEvoy Pada titik saya tidak menyarankan mereka bertemu di titik awal. Mereka bertemu lagi di awal siklus sebagaimana ditunjukkan dengan jelas oleh angka-angka itu.
skedastik
5

Pendekatan:

Ada dua petunjuk:

  • Pointer lambat yang menggerakkan satu simpul pada satu waktu.
  • Pointer cepat yang memindahkan dua node sekaligus.

Jika kedua penunjuk bertemu, itu membuktikan bahwa ada loop. Setelah mereka bertemu, salah satu simpul akan menunjuk ke kepala dan kemudian keduanya melanjutkan satu simpul pada satu waktu. Mereka akan bertemu di awal perulangan.

Dasar Pemikiran: Ketika dua orang berjalan di jalur yang melingkar, salah satunya dengan kecepatan dua kali lipat, di mana mereka bertemu? Persis di mana mereka mulai.

Sekarang, misalkan pelari cepat memiliki klangkah nawal di putaran langkah. dimana mereka akan bertemu? Tepat pada n-klangkah-langkah. Ketika pelari lambat telah membahas (n-k)langkah - langkah, pelari cepat akan membahas k+2(n-k)langkah - langkah. ( Yaitu, k+2n-2klangkah yaitu 2n-klangkah ). yaitu (n-k)langkah-langkah (Jalannya melingkar dan kami tidak peduli tentang jumlah putaran setelah mereka bertemu; Kami hanya tertarik pada posisi di mana mereka bertemu).

Sekarang bagaimana pelari cepat mendapatkan klangkah awal di tempat pertama? Karena butuh pelari lambat sehingga banyak langkah untuk mencapai awal loop. Jadi awal dari loop adalah k langkah dari simpul kepala.

Catatan: Node tempat kedua penunjuk bertemu berjarak beberapa klangkah dari awal lingkaran (di dalam lingkaran) dan simpul kepala juga berjarak beberapa klangkah dari awal putaran. Jadi ketika kita memiliki pointer yang maju pada kecepatan yang sama dengan 1 langkah dari bot node ini, mereka akan bertemu pada awal loop.

Saya percaya ini mudah. Tolong beri tahu saya jika ada bagian yang ambigu.

Aadith Ramia
sumber
4
Silakan kirim jawaban lengkap di sini, bukan hanya tautan yang mungkin rusak di masa mendatang
Leeor
4

Oke jadi mari kita asumsikan kelinci dan kura-kura bertemu pada titik yang k langkah menjauh dari awal siklus, jumlah langkah sebelum siklus dimulai adalah mu dan panjang siklus adalah L.

Jadi sekarang di titik pertemuan ->

Jarak yang dicakup oleh kura-kura = mu + a * L + k - Persamaan 1

(Langkah-langkah yang diambil untuk mencapai awal siklus + langkah-langkah yang diambil untuk membahas iterasi siklus 'a' dari awal siklus) (di mana a adalah konstanta positif)

Jarak yang dicakup oleh kelinci = mu + b * L + k - Persamaan 2

(Langkah-langkah yang diambil untuk mencapai awal siklus + langkah-langkah yang diambil untuk mencakup iterasi 'b' dari siklus + k langkah-langkah dari awal siklus) (di mana b adalah konstanta positif dan b> = a)

Jadi jarak ekstra yang dicakup oleh kelinci adalah = Persamaan 2 - Persamaan 1 = (ba) * L

Harap dicatat bahwa jarak ini juga sama dengan jarak kura-kura dari titik awal karena kelinci bergerak 2 kali lebih cepat daripada kura-kura. Ini dapat disamakan dengan 'mu + k' yang juga merupakan jarak dari titik pertemuan dari awal jika kita tidak menyertakan banyak lintasan lintas siklus.

Dengan demikian, mu + k = (ba) * L

Jadi langkah mu dari titik ini akan mengarah kembali ke awal siklus (karena langkah k dari awal siklus telah diambil untuk mencapai titik pertemuan). Ini bisa terjadi dalam siklus yang sama atau siklus berikutnya. Jadi sekarang jika kita memindahkan kura-kura ke awal daftar terkait, itu akan mengambil langkah mu untuk mencapai titik awal siklus dan kelinci akan mengambil langkah mu untuk juga mencapai awal siklus dan dengan demikian mereka berdua akan bertemu di titik awal siklus.

PS Jujur, saya memiliki pertanyaan yang sama dengan poster asli di pikiran saya dan saya membaca jawaban pertama, mereka benar-benar membersihkan beberapa hal tetapi saya tidak dapat mencapai hasil akhir dengan jelas sehingga saya mencoba melakukannya dengan cara saya sendiri dan merasa lebih mudah dimengerti.

Prateek Jassal
sumber
mereka biasanya tidak bertemu di awal siklus
Warren MacEvoy
3

masukkan deskripsi gambar di sini kredit gambar

Panggilan jarak jumlah link yang diikuti oleh pointer, dan waktu jumlah iterasi algoritma yang dibutuhkan untuk memindahkan pointer lambat satu link dan pointer cepat dua link. Ada N node sebelum siklus panjang C, diberi label dengan siklus offset k = 0 hingga C-1.

Untuk mencapai awal siklus, lambat membutuhkan waktu dan jarak N. Ini berarti cepat mengambil jarak N dalam siklus (N untuk sampai di sana, N untuk berputar). Jadi pada waktu N, lambat pada siklus offset k = 0, dan cepat pada siklus offset k = N mod C.

Jika N mod C nol, lambat dan cepat sekarang cocok dan siklus ditemukan pada waktu N dan posisi siklus k = 0.

Jika N mod C bukan nol, maka fast sekarang harus mengejar ketinggalan dengan lambat, yang pada saat N adalah C- (N mod C) jarak di belakang dalam siklus.

Karena gerakan cepat 2 untuk setiap 1 lambat, mengurangi jarak oleh 1 pada setiap iterasi, ini membutuhkan waktu tambahan sebanyak jarak antara cepat dan lambat pada waktu N, yaitu C- (N mod C). Karena lambat bergerak dari offset 0, ini juga merupakan offset tempat mereka bertemu.

Jadi, jika N mod C adalah nol, fase 1 berhenti setelah iterasi N pada awal siklus. Jika tidak, fase 1 berhenti setelah iterasi N + C- (N mod C) pada offset C- (N mod C) ke dalam siklus.

// C++ pseudocode, end() is one after last element.

int t = 0;
T *fast = begin();
T *slow = begin();
if (fast == end()) return [N=0,C=0];
for (;;) {
    t += 1;
    fast = next(fast);
    if (fast == end()) return [N=(2*t-1),C=0];
    fast = next(fast);
    if (fast == end()) return [N=(2*t),C=0];
    slow = next(slow);
    if (*fast == *slow) break;
}

Ok, jadi fase 2: lambat mengambil N langkah lebih lanjut untuk sampai ke siklus, di mana titik cepat (sekarang bergerak 1 per langkah waktu) berada di (C- (N mod C) + N) mod C = 0. Jadi mereka bertemu di awal siklus setelah fase 2.

int N = 0;
slow = begin();
for (;;) {
    if (*fast == *slow) break;
    fast = next(fast);
    slow = next(slow);
    N += 1;
}

Untuk kelengkapan, fase 3 menghitung panjang siklus dengan bergerak sekali lagi melalui siklus:

int C = 0;
for (;;) {
    fast = next(fast);
    C += 1;
    if (fast == slow) break;
}
Warren MacEvoy
sumber
Tautan ke google doc untuk mensimulasikan algoritma: docs.google.com/spreadsheets/d/…
Warren MacEvoy
1
Perhatikan bahwa, jika N <= C, iterasi berhenti setelah iterasi C. Dalam setiap kasus itu harus berhenti dalam kurang dari N + C langkah dan tidak mungkin berhenti pada awal siklus
Warren MacEvoy
2

Kurangi masalah menjadi masalah berulang, lalu kembali ke masalah awal

Saya menemukan penjelasan berikut ini lebih intuitif.

  1. Ambil dua petunjuk ( 1 = kura-kura dan 2 = kelinci) yang dimulai dari kepala ( O ), 1 memiliki panjang langkah 1 , 2 memiliki panjang langkah 2 . Pikirkan saat ketika 1 mencapai simpul awal dari siklus itu ( A ).

    Kami ingin menjawab pertanyaan berikut "Di mana 2 ketika 1 berada di A?" .

    Jadi, OA = aadalah bilangan alami ( a >= 0). Tetapi dapat ditulis dengan cara berikut:, di a = k*n + bmana a, k, n, b are natural numbers:

    • n = panjang siklus
    • k >= 0 = konstan
    • 0 <= b <= n-1

    Itu artinya b = a % n.

    Misalnya: jika a = 20dan n = 8=> k = 2dan b = 4karena 20 = 2*8 + 4.

    Jarak yang dicakup oleh 1 adalah d = OA = a = k*n + b. Tetapi pada saat yang sama, 2 mencakup D = 2*d = d + d = OA + d = OA + k*n + b. Ini berarti bahwa ketika 2 berada di A ia harus menutup k*n + b. Seperti yang Anda lihat, kadalah jumlah lap, tapi setelah mereka lap, 2 akan b jauh dari A. Jadi, kami menemukan di mana 2 adalah ketika 1 adalah di A. Mari panggilan titik B, di mana AB = b.

    masukkan deskripsi gambar di sini

  2. Sekarang, kami mengurangi masalah menjadi lingkaran. Pertanyaannya adalah "Di mana titik pertemuannya?" . Di mana C itu ?

    masukkan deskripsi gambar di sini

    Dalam setiap langkah, 2 mengurangi jarak dari 1 dengan 1(katakanlah meter) karena 1 semakin jauh dari 2 dengan 1, tetapi pada saat yang sama 2 semakin mendekati 1 oleh 2.

    Jadi, persimpangan akan menjadi ketika jarak antara 1 dan 2 akan menjadi nol. Ini berarti bahwa 2 mengurangi n - bjarak. Untuk mencapai ini, 1 akan membuat n - blangkah, sedangkan 2 akan membuat 2*(n - b)langkah.

    Jadi, titik persimpangan akan n - bjauh dari A (searah jarum jam), karena ini adalah jarak yang dicakup oleh 1 hingga bertemu 2 . => jarak antara C dan A adalah CA = b, karena AC = AB + BC = n - bdan CA = n - AC. Jangan berpikir bahwa AC = CA, karena ACjarak itu bukan jarak matematis sepele, ini adalah jumlah langkah antara A dan C (di mana A adalah titik awal dan C adalah titik akhir).

  3. Sekarang, mari kita kembali ke skema awal.

    Kami tahu itu a = k*n + bdan CA = b.

    Kita dapat mengambil 2 pointer baru 1 ' dan 1' ' , di mana 1' dimulai dari kepala ( O ) dan 1 '' mulai dari titik persimpangan ( C ).

    Sementara 1 ' pergi dari O ke A , 1' ' pergi dari C ke A dan terus menyelesaikan kputaran. Jadi, titik persimpangan adalah A .

    masukkan deskripsi gambar di sini

    masukkan deskripsi gambar di sini

ROMANIA_engineer
sumber
2

masukkan deskripsi gambar di sini

Jika pointer bertemu pada titik P seperti yang ditunjukkan pada gambar, jarak Z + Y adalah titik P dan X + Y juga merupakan titik P yang berarti Z = X. Itulah sebabnya menjaga memindahkan satu pointer dari P dan memindahkan yang lain dari awal (S) hingga mereka bertemu, yang berarti memindahkan jarak yang sama (Z atau X) ke titik yang sama M (jarak Z dari P dan X dari S) akan menjadi mulai dari loop. Sederhana!

pengguna9639921
sumber
1

Dengan semua analisis di atas, jika Anda adalah orang yang belajar melalui contoh, saya mencoba untuk menulis analisis singkat dan contoh yang membantu menjelaskan matematika yang orang lain coba jelaskan. Kita mulai!

Analisis:

Jika kita memiliki dua pointer, satu lebih cepat dari yang lain, dan memindahkannya bersama, mereka akhirnya akan bertemu lagi untuk menunjukkan siklus atau nol untuk menunjukkan tidak ada siklus.

Untuk menemukan titik awal siklus, biarkan ...

  1. m menjadi jarak dari kepala ke awal siklus;

  2. d menjadi jumlah node dalam siklus;

  3. p1 menjadi kecepatan dari pointer yang lebih lambat;

  4. p2menjadi kecepatan penunjuk yang lebih cepat, mis. 2 berarti langkah melalui dua node sekaligus.

    Perhatikan iterasi berikut:

 m = 0, d = 10:
 p1 = 1:  0  1  2  3  4  5  6  7  8  9 10 // 0 would the start of the cycle
 p2 = 2:  0  2  4  6  8 10 12 14 16 18 20

 m = 1, d = 10:
 p1 = 1: -1  0  1  2  3  4  5  6  7  8  9
 p2 = 2: -1  1  3  5  7  9 11 13 15 17 19

 m = 2, d = 10:
 p1 = 1: -2 -1  0  1  2  3  4  5  6  7  8
 p2 = 2: -2  0  2  4  6  8 10 12 14 16 18

Dari data sampel di atas, kita dapat dengan mudah menemukan bahwa kapan pun pointer yang lebih cepat dan lebih lambat bertemu, mereka berada beberapa mlangkah dari awal siklus. Untuk mengatasi ini, letakkan penunjuk yang lebih cepat kembali di kepala dan atur kecepatannya ke kecepatan penunjuk yang lebih lambat. Ketika mereka bertemu lagi, simpul adalah awal dari siklus.

Steve
sumber
1

Katakanlah,

N[0] is the node of start of the loop, 
m is the number of steps from beginning to N[0].

kami memiliki 2 pointer A dan B, A berjalan pada kecepatan 1x, B pada kecepatan 2x, keduanya dimulai dari awal.

ketika A mencapai N [0], B seharusnya sudah dalam N [m]. (Catatan: A menggunakan langkah m untuk mencapai N [0], dan B harus langkah m lebih lanjut)

Kemudian, A menjalankan k lebih banyak langkah untuk bertabrakan dengan B, yaitu A berada di N [k], B berada di N [m + 2k] (Catatan: B harus menjalankan langkah 2k mulai dari N [m])

A bertabrakan B pada N [k] dan N [m + 2k], artinya k = m + 2k, sehingga k = -m

Jadi, untuk kembali ke N [0] dari N [k], kita perlu lebih banyak langkah.

Cukup dengan mengatakan, kita hanya perlu menjalankan lebih banyak langkah setelah kita menemukan node collision. Kita dapat memiliki pointer untuk dijalankan dari awal dan pointer berjalan dari collision node, mereka akan bertemu di N [0] setelah langkah m.

Oleh karena itu, kode pseudo adalah sebagai berikut:

1) A increase 1 step per loop
2) B increase 2 steps per loop
3) if A & B are the same node, cycle found, then go to 5
4) repeat from 1
5) A reset to head
6) A increase 1 step per loop
7) B increase 1 step per loop
8) if A & B are the same node, start of the cycle found
9) repeat from 6
phdfong - Kenneth Fong
sumber
1

Saya tidak berpikir begitu benar bahwa ketika mereka bertemu itu adalah titik awal. Tapi ya jika pointer lainnya (F) berada di titik pertemuan sebelumnya, maka pointer tersebut akan berada di akhir loop, bukan di awal loop dan pointer (S) yang dimulai dari awal daftar itu akan berakhir di awal loop. untuk misalnya:

1->2->3->4->5->6->7->8->9->10->11->12->13->14->15->16->17->18->19->20->21->22->23->24->8

Meet at :16

Start at :8

public Node meetNodeInLoop(){

    Node fast=head;
    Node slow=head;

    fast=fast.next.next;
    slow=slow.next;

    while(fast!=slow){

        fast=fast.next;
        fast=fast.next;

        if(fast==slow) break; 

        slow=slow.next;
    }

    return fast;

}

public Node startOfLoop(Node meet){

    Node slow=head;
    Node fast=meet;

    while(slow!=fast){
        fast=fast.next;
        if(slow==fast.next) break;
        slow=slow.next;
    }

    return slow;
}
MrA
sumber
1

Penjelasan sederhana menggunakan gagasan kecepatan relatif yang diajarkan di sekolah menengah - Fisika 101 / Kinematika kuliah.

Lingkaran di LinkedList

  1. Mari kita asumsikan jarak dari awal daftar tertaut ke mulai dari lingkaran adalah xhop. Mari kita sebut awal lingkaran sebagai titik X(dalam huruf besar - lihat gambar di atas). Juga mari kita asumsikan ukuran lingkaran adalah N hop.

  2. Kecepatan kelinci = 2 * Kecepatan kura-kura. Jadi itu 1 hops/secdan 2 hops/secmasing - masing

  3. Ketika kura-kura mencapai awal lingkaran X, kelinci harus xmelompat jauh pada titik Ydalam gambar. (Karena kelinci telah menempuh jarak dua kali lipat dari kura-kura).

  4. Dengan demikian, panjang busur yang tersisa searah jarum jam dari X ke Y adalah N-x. Ini juga merupakan jarak relatif yang harus ditempuh antara kelinci dan kura-kura agar mereka dapat bertemu . Katakanlah jarak relatif ini akan dibahas dalam waktu t_myaitu waktu untuk bertemu. Kecepatan relatif (2 hops/sec - 1 hops/sec)yaitu 1 hops/sec. Dengan menggunakan, jarak relatif = kecepatan relatif X waktu, kita dapatkan, t= N-xdtk. Jadi akan dibutuhkan N-xuntuk mencapai titik pertemuan untuk kura-kura dan kelinci.

  5. Sekarang dalam N-xdetik dan dengan 1 hops/seckecepatan, kura-kura yang sebelumnya pada titik Xakan mencakup Nx hop untuk mencapai titik pertemuan M. Jadi, itu berarti titik pertemuan Mberada di N-xberlawanan berlawanan arah jarum jam dari X= (yang selanjutnya menyiratkan) => bahwa ada xjarak yang tersisa dari titik Mke Xarah jarum jam.

  6. Tetapi xjuga jarak untuk mencapai titik Xdari awal daftar tertaut.

  7. Sekarang, kami tidak peduli dengan jumlah hop yang xsesuai. Jika kita meletakkan satu kura-kura di awal LinkedList dan satu kura-kura di titik pertemuan Mdan membiarkan mereka melompat / berjalan, maka mereka akan bertemu di titik X, yang merupakan titik (atau simpul) yang kita butuhkan.

Pranjal Mittal
sumber
1

Mengerjakan ini dengan diagram akan membantu. Saya mencoba menjelaskan masalah tanpa persamaan.

  1. Jika kita membiarkan kelinci dan kura-kura berlari dalam lingkaran dan kelinci berlari dua kali kura-kura maka, pada akhir satu putaran untuk kura-kura kelinci akan setengah. Pada akhir dua lap dari kura-kura kelinci akan melakukan 1 putaran dan mereka berdua bertemu. Ini berlaku untuk semua kecepatan seperti jika kelinci berlari tiga kali, kelinci 1 putaran sama dengan 1/3 dari kura-kura sehingga pada akhir 3 putaran untuk kura-kura kelinci akan menutupi 1 putaran dan mereka bertemu.
  2. Sekarang jika kita mulai m langkah sebelum loop, maka itu berarti kelinci lebih cepat mulai di depan dalam loop. Jadi, jika kura-kura mencapai awal loop, kelinci adalah m langkah di depan loop dan ketika mereka bertemu itu akan menjadi langkah m sebelum loop dimulai.
shiva kumar
sumber
1

-ada langkah k sebelum loop. Kami tidak tahu apa itu k dan tidak perlu mencari tahu. Kita dapat bekerja secara abstrak hanya dengan k.

--Setelah k langkah

----- T pada awal siklus

----- H adalah k langkah ke dalam siklus (dia pergi total 2k dan dengan demikian k ke loop)

** mereka sekarang melenggang - k terpisah

(catat bahwa k == K == mod (loopsize, k) --eg jika sebuah simpul 2 langkah ke dalam siklus 5 simpul juga 7, 12 atau 392 langkah masuk, jadi seberapa besar siklusnya, k tidak faktor dalam.

Karena mereka mengejar satu sama lain dengan kecepatan 1 langkah per unit waktu karena satu bergerak dua kali lebih cepat daripada yang lain, mereka akan bertemu di loopsize - k.

Ini berarti akan membutuhkan k node untuk mencapai awal siklus dan dengan demikian jarak dari head ke cyclestart dan collision ke cyclestart adalah sama.

Jadi sekarang setelah tabrakan pertama pindah T kembali ke kepala. T dan H akan bertemu di cyclestart jika Anda bergerak dengan laju masing-masing 1. (dalam langkah k untuk keduanya)

Ini berarti bahwa algoritma tersebut adalah:

  • dari head move T = t.next dan H.next.next sampai mereka bertabrakan (T == H) (ada siklus)

// atasi case ketika k = 0 atau T dan H bertemu di bagian atas loop dengan menghitung panjang loop

--hitung panjang siklus dengan menggerakkan T atau H di sekitarnya dengan penghitung

--memindahkan pointer T2 ke kepala daftar

--memindahkan panjang pointer langkah-langkah siklus

--move pointer H2 lainnya ke kepala

- Pindahkan T2 dan H2 bersama-sama sampai mereka bertemu di awal siklus

itu dia!

Rumah Minum Teh Droid
sumber
1

Sudah ada banyak jawaban untuk ini, tetapi saya pernah membuat diagram untuk ini yang lebih intuitif secara visual bagi saya. Mungkin itu bisa membantu orang lain.

Aha-momen utama bagi saya adalah:

  • Membagi T (kura-kura) menjadi T1 (pre-loop) dan T2 (in-loop). T = kura-kura, H = kelinci

  • Kurangi T dari H , di mana mereka tumpang tindih secara visual. Apa yang tetap ( H - T = H' ) sama dengan T .

  • Matematika yang tersisa cukup sederhana. Dari H, kurangi di mana T tumpang tindih secara visual
mhelvens
sumber
-1

Saya tahu sudah ada jawaban yang diterima untuk masalah ini, tetapi saya akan tetap mencoba menjawab dengan lancar. Menganggap :

The length of the Path is 'X+B' where 'B' is the length of the looped path and X of the non looped path. 
    Speed of tortoise : v
    Speed of hare     : 2*v 
    Point where both meet is at a distance 'x + b - k' from the starting point.

Sekarang, biarkan kelinci dan kura-kura bertemu setelah waktu 't' dari awal.

Pengamatan:

Jika, Jarak yang ditempuh oleh kura-kura = v * t = x + (bk) (katakanlah)

Kemudian, Jarak yang ditempuh oleh kelinci = 2 * v * t = x + (b - k) + b (karena kelinci telah melewati bagian yang dililitkan sekali)

Sekarang, waktu pertemuan di sana sama.

=> x + 2 * b - k = 2 * (x + b - k)

=> x = k

Ini tentu saja berarti bahwa panjang jalur yang tidak dilingkarkan sama dengan jarak dari titik awal loop dari titik di mana keduanya bertemu.

n0nChun
sumber
Anda tidak dapat mengasumsikan bahwa kura-kura itu bepergian dengan tepat x + bk pada saat mereka bertemu. Juga, saya tidak mengerti bagaimana Anda mendapat x + 2 * bk untuk jarak kelinci.
Plumenator
Karena kelinci akan melintasi bagian yang dililitkan sekali harus bertemu dengan kura-kura .. Saya tidak menjelaskannya di sana: /
n0nChun
-1

Sebenarnya mudah untuk membuktikan bahwa mereka berdua akan bertemu di titik awal, jika Anda mempertimbangkan matematika di belakang titik pertemuan.
Pertama biarkan m menunjukkan titik awal siklus dalam daftar yang ditautkan, dan n menunjukkan panjang siklus. Kemudian agar kelinci dan kura-kura bertemu, kita memiliki:

( 2*t - m )%n = (t - m) %n, where t = time (at t = 0 , both are at the start)

Menyatakan ini secara lebih matematis:

(2*t - m - (t - m) ) = 0 modulo n , which implies , t = 0 modulo n 

sehingga mereka akan bertemu pada waktu t yang seharusnya merupakan kelipatan dari panjang siklus. Ini berarti bahwa mereka bertemu di suatu lokasi, yaitu (t-m) modulo n = (0-m) modulo n = (-m) modulo n.

Jadi sekarang kembali ke pertanyaan, jika Anda memindahkan satu pointer dari awal daftar tertaut, dan satu lagi dari titik persimpangan, setelah langkah m kita akan memiliki kelinci (yang bergerak di dalam siklus) datang ke titik yang ((-m) + m) modulo n = 0 modulo nyang tidak lain adalah titik awal dari siklus. Jadi kita dapat melihat bahwa setelah m langkah-langkah datang ke awal siklus dan kura-kura akan bertemu di sana karena akan melintasi m langkah-langkah dari awal daftar terkait.

Sebagai catatan tambahan, kita juga dapat menghitung waktu persimpangan mereka dengan cara ini: Kondisi t = 0 modulo nmemberi tahu kita bahwa mereka akan bertemu pada waktu yang merupakan kelipatan dari panjang siklus, dan juga t harus lebih besar dari m seperti yang akan mereka temui di siklus. Jadi waktu yang diambil akan sama dengan kelipatan pertama dari n yang lebih besar dari m .

pengguna1011
sumber
Mereka belum tentu bertemu di awal siklus.
Warren MacEvoy
-1

Misalkan pointer Anda bertemu di persimpangan titik y dan z.

n dan m adalah jumlah loop yang lebih cepat dan pointer yang lebih lambat masing-masing dibutuhkan sebelum pertemuan.

Lihat gambar untuk sisa buktinya. Temukan titik awal loop dalam daftar tertaut

Ashish Goyal
sumber