Solusi Leetcode - Linked List Cycle

Mendeteksi cycle di linked list adalah soal interview klasik. Solusi pertama saya pakai Set untuk melacak node yang udah dikunjungi, yang memang jalan tapi pakai space O(n). Lalu saya belajar tentang fast and slow pointers (Floyd's Cycle Detection Algorithm). Teknik ini cukup pakai space O(1).

Di dalam cycle, fast pointer maju dua node setiap iterasi dan slow pointer maju satu. Posisi relatif mereka berulang modulo panjang cycle, jadi kedua pointer pasti bertemu. Nggak perlu ada catatan node yang udah dikunjungi.

Memahami Soalnya

Diberikan sebuah linked list, tentukan apakah list itu punya cycle. Cycle artinya ada node yang menunjuk balik ke node sebelumnya, sehingga terbentuk loop. Tantangannya adalah mendeteksi ini secara efisien, idealnya tanpa extra space yang sebanding dengan ukuran list.

Pendekatan Pertama Saya

Saya pakai Set untuk mencatat node yang udah dikunjungi. Node yang muncul lagi menandakan ada cycle.

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
}

Set itu mencatat setiap node yang dikunjungi dan butuh extra space O(n). Dua pointer bisa mendeteksi cycle tanpa koleksi itu.

Insight dari Fast and Slow Pointers

Lalu saya belajar tentang Floyd's Cycle Detection Algorithm (juga disebut algoritma "tortoise and hare"). Aturannya seperti ini:

• Pakai dua pointer yang bergerak dengan kecepatan berbeda
• Slow pointer bergerak satu langkah setiap kali
• Fast pointer bergerak dua langkah setiap kali
• Di dalam cycle, kedua pointer akhirnya bertemu
• Tanpa cycle, fast pointer atau link next-nya bakal sampai ke null

Begitu kedua pointer masuk ke cycle, jarak relatif mereka berubah 1 setiap iterasi (fast bergerak 2, slow bergerak 1). Dalam satu panjang cycle, posisi mereka bakal sama.

Implementasi fast and slow pointer

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 1 step
        fast = fast.next.next; // Move fast 2 steps
    }
    
    return false; // Fast hit null, no cycle
}

Trace pointer

Untuk list yang punya cycle, pointer-nya bergerak seperti ini:

List dengan cycle: 1 → 2 → 3 → 4 → 5 → 3 (menunjuk balik ke 3)

• Awal: slow = 1, fast = 2
• Langkah 1: slow = 2, fast = 4 (fast bergerak 2 langkah)
• Langkah 2: slow = 3, fast = 3 (fast bergerak dari 4→5→3, slow bergerak 2→3)
• slow === fast → return true!

List tanpa cycle: 1 → 2 → 3 → 4 → null

• Awal: slow = 1, fast = 2
• Langkah 1: slow = 2, fast = 4
• Loop-nya berhenti di slow = 2, fast = 4 karena fast.next bernilai null
• Return false

Kenapa Ini Berhasil

Algoritma ini bekerja karena sifat matematis berikut:

• Ada cycle: Kedua pointer masuk ke cycle. Setelah itu, posisi mereka pasti sama dalam satu panjang cycle.
• Tanpa cycle: Loop-nya berhenti waktu fast pointer atau link next-nya bernilai null
• Jarak relatif: Setiap iterasi mengubah jarak relatif sebesar 1 modulo panjang cycle (fast bergerak 2, slow bergerak 1).

Analisis Kompleksitas

Time Complexity: O(n)

• Di worst case (nggak ada cycle), kita menelusuri list sekali: O(n)
• Setelah kedua pointer masuk ke cycle, mereka bertemu dalam satu panjang cycle: tetap O(n)
• Setiap langkah bernilai O(1), jadi secara keseluruhan O(n)

Space Complexity: O(1)

• Cuma pakai dua variabel pointer
• Nggak ada struktur data tambahan
• Space-nya konstan berapa pun ukuran list-nya

Jebakan Umum

Waktu mengimplementasikan ini, hati-hati dengan:

1. Null pointer error: Selalu cek fast !== null && fast.next !== null sebelum mengakses fast.next.next
2. Edge case: Tangani list kosong dan list dengan satu node. Satu node bisa membentuk cycle kalau dia menunjuk ke dirinya sendiri.
3. Posisi awal: Beberapa implementasi memulai kedua pointer dari head, tapi memulai fast dari head.next menghindari pengecekan kesamaan di awal
4. Infinite loop: Pastikan kondisi loop kamu menangani kasus null dengan benar

Mencari Awal Cycle (Bonus)

Kalau kamu perlu mencari di mana cycle-nya dimulai, kamu bisa mengembangkan algoritma ini:

function detectCycleStart(head) {
    // First, detect if there's a cycle
    let slow = head;
    let fast = head;
    
    while (fast !== null && fast.next !== null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow === fast) break; // Found meeting point
    }
    
    if (fast === null || fast.next === null) return null; // No cycle
    
    // Move one pointer to head, keep other at meeting point
    // Move both one step at a time - they'll meet at cycle start
    slow = head;
    while (slow !== fast) {
        slow = slow.next;
        fast = fast.next;
    }
    
    return slow; // This is the cycle start
}

Ringkasan deteksi cycle

• Fast and slow pointers mendeteksi cycle dalam O(n) time dan O(1) space tanpa menyimpan node yang udah dikunjungi
• Teknik ini berhasil karena cycle menciptakan skenario "catch-up"
• Pola ini muncul di soal deteksi cycle lainnya (kayak Happy Number)
• Algoritma Floyd adalah contoh klasik pemanfaatan sifat matematis untuk mengoptimasi algoritma

Soal ini menunjukkan ke saya gimana teknik fast and slow pointers memanfaatkan struktur list itu sendiri, bukan storage tambahan. Pola yang sama berlaku di soal deteksi cycle lainnya.