Deteksi cycle dari Floyd memakai dua reference: satu maju satu node setiap langkah, yang lain maju dua. Kalau linked list berputar, reference yang lebih cepat akhirnya menyusul yang lebih lambat. Kita nggak perlu mencatat node yang udah dikunjungi.
Mendeteksi cycle tanpa set
Cycle terjadi kalau mengikuti link next membawa kita kembali ke node yang udah dikunjungi. Tugasnya mengembalikan true kalau ada cycle dan false kalau list berakhir di null. Set bisa menyimpan node yang udah dikunjungi:
function hasCycleNaive(head) {
let seen = new Set();
while (head !== null) {
if (seen.has(head)) {
return true; // Found a cycle!
}
seen.add(head);
head = head.next;
}
return false; // No cycle
}
Metode berbasis set ini benar, tapi set-nya ikut membesar seiring panjang list, jadi extra space-nya O(n).
Metode two pointer dari Floyd
Dengan dua pointer, slow maju satu node dan fast maju dua. Kalau fast atau fast.next mencapai null, list punya ujung. Kalau ada cycle, kedua pointer akhirnya bertemu di dalamnya.
function hasCycle(head) {
if (head === null || head.next === null) {
return false; // An empty list or a null next link cannot form a cycle
}
let slow = head; // Moves 1 step at a time
let fast = head.next; // Moves 2 steps at a time
while (fast !== null && fast.next !== null) {
if (slow === fast) {
return true; // They met! There's a cycle
}
slow = slow.next; // Move slow pointer 1 step
fast = fast.next.next; // Move fast pointer 2 steps
}
return false; // Fast pointer hit null, no cycle
}
Begitu kedua pointer ada di dalam cycle, posisi mereka berulang modulo panjang cycle. Pointer cepat mendekat satu node ke pointer lambat di setiap iterasi, jadi jarak relatif mereka akhirnya jadi nol. Pengecekan null menangani list tanpa cycle sebelum salah satu pointer di-dereference.
Kompleksitas dan penerapannya
Metode yang sama bisa dipakai pada urutan lain kalau setiap posisi punya tepat satu posisi berikutnya:
- Verifikasi symlink: Mendeteksi symbolic link yang melingkar di file system
- Pengecekan dependency di compiler: Cek apakah ada cycle ketika setiap module dalam urutan cuma punya satu dependency berikutnya
Loop pointer ini butuh O(n) waktu dan O(1) extra space.
Syarat satu langkah berikutnya itu penting. Kalau dependency bercabang ke beberapa node, algoritma ini saja nggak menelusuri seluruh graph.

Memuat komentar...