LeetCode Grinding
Algorithms3 menit baca

Solusi Leetcode - Linked List Cycle

Membandingkan set berisi node yang udah dikunjungi dengan algoritma Floyd untuk mendeteksi cycle di linked list.

Di artikel ini 9 bagian

Linked list yang punya cycle nggak pernah mencapai link null. Mencatat node yang dikunjungi bisa mendeteksi putaran itu, tapi dua pointer dengan kecepatan berbeda cukup memakai O(1) extra space.

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.

Mencatat node yang dikunjungi

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

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
}

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

Fast and slow pointers

Deteksi cycle dari Floyd memajukan satu pointer satu node dan pointer lainnya dua node:

  • 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

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

  • 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

  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

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

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

Versi pencarian awal cycle memulai kedua pointer dari head dan membandingkannya setelah bergerak. Pertahankan inisialisasi itu saat memakai fase keduanya untuk mencari node awal cycle.

Topik

Makasih udah baca

Gimana menurutmu?

Kasih reaksi atau komentar di bawah.

Memuat reaksi…

Bagikan tulisan ini

Memuat komentar...

Tulisan terkait

Semua tulisan