LeetCode Grinding
Algorithms2 menit baca

Teknik Fast and Slow Pointers

Pakai dua pointer dengan kecepatan berbeda untuk mendeteksi cycle tanpa menyimpan kumpulan node yang udah dikunjungi.

Di artikel ini 3 bagian

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:

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

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

Topik

Makasih udah baca

Gimana menurutmu?

Kasih reaksi atau komentar di bawah.

Memuat reaksi…

Bagikan tulisan ini

Memuat komentar...

Tulisan terkait

Semua tulisan