Teknik Fast and Slow Pointers

Mendeteksi cycle di linked list nggak perlu menyimpan setiap node yang udah dikunjungi. Metode fast and slow pointer dari Floyd cuma memakai dua reference dan O(1) extra space. Waktu pertama kali lihat metode ini, saya nggak menyangka dua reference aja udah cukup.

Mendeteksi cycle tanpa set

Cycle terjadi ketika sebuah node menunjuk balik ke node sebelumnya, sehingga kalau kita mengikuti link next, kita nggak akan pernah sampai ke null. Tugasnya adalah mengembalikan true kalau ada cycle dan false untuk list yang punya ujung. Awalnya saya pakai Set untuk mencatat 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

Lalu saya belajar teknik fast and slow pointers. Satu pointer bergerak satu node setiap langkah, sementara yang lain bergerak dua. Kalau list-nya punya ujung, fast atau fast.next bakal sampai ke null. Kalau list-nya berputar, kedua pointer masuk ke cycle, dan pointer yang lebih cepat akhirnya menyusul yang lebih lambat. Implementasinya:

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

Saya kaget waktu tahu ide yang sama juga berguna di luar linked list:

• 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-nya butuh O(n) time. Extra space-nya O(1). Algoritma ini memanfaatkan cycle itu sendiri, bukan set terpisah untuk node yang udah dikunjungi.

Fast and slow pointers layak jadi pilihan default setiap kali sebuah urutan mungkin berputar dan setiap langkahnya bisa dihitung dari posisi saat ini. Teknik ini mengganti penyimpanan state kunjungan sebesar O(n) dengan sejumlah pointer yang konstan.