0Pricing
Coding Interview Prep · Pelajaran

Deteksi Siklus dengan Algoritma Floyd

Deteksi siklus menggunakan pendekatan pointer lambat-cepat, temukan titik masuk siklus, dan buktikan kebenaran algoritma secara matematis.

Deteksi Siklus dengan Algoritma Floyd adalah pelajaran Coding Interview Prep gratis di CoddyKit. Ini adalah pelajaran 3 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Coding Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Coding Interview Prep mencakup 4 pelajaran total.

Apa Itu Siklus dalam Daftar Tertaut?

Siklus dalam daftar tertaut terjadi ketika penunjuk next suatu simpul menunjuk kembali ke simpul yang telah dikunjungi, sehingga menciptakan perulangan tanpa akhir. Menelusuri daftar semacam itu dengan perulangan while head akan berjalan selamanya. Deteksi siklus merupakan soal wawancara klasik dan dasar bagi algoritma penunjuk yang lebih lanjut.

Pendekatan naif menyimpan setiap simpul yang telah dikunjungi dalam sebuah himpunan dan memeriksa keanggotaannya—waktu O(n), ruang O(n). Algoritma Floyd menyelesaikan soal yang sama dalam waktu O(n) dan ruang O(1), yang diharapkan oleh pewawancara.

Algoritma Penunjuk Lambat-Cepat Floyd

Deteksi siklus Floyd ("kura-kura dan kelinci") menggunakan dua penunjuk: slow maju satu langkah setiap kali, sedangkan fast maju dua langkah. Jika tidak ada siklus, penunjuk cepat mencapai nilai kosong terlebih dahulu. Jika ada siklus, penunjuk cepat pada akhirnya menyusul penunjuk lambat di dalam siklus dan keduanya bertemu pada simpul yang sama. Pertemuan tersebut membuktikan bahwa siklus ada.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def hasCycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

# Build: 3 -> 2 -> 0 -> -4 -> (back to 2)
nodes = [ListNode(v) for v in [3, 2, 0, -4]]
for i in range(3):
    nodes[i].next = nodes[i+1]
nodes[3].next = nodes[1]   # cycle: -4 -> 2

print(hasCycle(nodes[0]))  # True

Mengapa Penunjuk Lambat dan Cepat Selalu Bertemu

Secara informal: setelah kedua penunjuk memasuki siklus, jarak di antara keduanya berubah sebesar 1 setiap langkah (penunjuk cepat bertambah 2, penunjuk lambat bertambah 1, sehingga jaraknya berkurang 1 pada setiap putaran). Pada akhirnya jaraknya menjadi 0—keduanya berada pada simpul yang sama. Secara lebih formal, jika siklus memiliki panjang C, jarak maksimum di dalam siklus adalah C-1, dan jarak tersebut berkurang sebesar 1 pada setiap langkah, sehingga keduanya bertemu dalam waktu paling lama C langkah setelah sama-sama memasuki siklus.

Total langkah sebelum bertemu: paling banyak O(n + C) = O(n) karena C <= n.

# Visualise convergence: simulate gap in cycle
cycle_length = 5
for start_gap in range(1, cycle_length + 1):
    gap = start_gap
    steps = 0
    while gap != 0:
        gap = (gap - 1) % cycle_length
        steps += 1
    print(f'Start gap {start_gap}: meet after {steps} step(s)')

Menemukan Titik Masuk Siklus

Setelah mendeteksi siklus, algoritma Floyd juga dapat menemukan simpul masuk (tempat siklus dimulai). Setelah penunjuk lambat dan cepat bertemu di dalam siklus, kembalikan salah satu penunjuk ke kepala dan biarkan penunjuk lainnya tetap di titik pertemuan. Kemudian majukan keduanya satu langkah setiap kali. Keduanya akan bertemu tepat di simpul masuk siklus. Hal ini berhasil karena jarak dari kepala ke titik masuk sama dengan jarak dari titik pertemuan ke titik masuk (modulo panjang siklus).

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def detectCycle(head):
    slow = fast = head
    # Phase 1: detect meeting point
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            break
    else:
        return None  # no cycle
    # Phase 2: find entry
    pointer = head
    while pointer is not slow:
        pointer = pointer.next
        slow    = slow.next
    return pointer  # cycle entry node

nodes = [ListNode(v) for v in [3, 2, 0, -4]]
for i in range(3):
    nodes[i].next = nodes[i+1]
nodes[3].next = nodes[1]  # entry is nodes[1] (val=2)

entry = detectCycle(nodes[0])
print(entry.val)  # 2

Pembuktian Matematis Simpul Masuk

Misalkan F = jarak dari kepala ke titik masuk siklus, C = panjang siklus, dan a = jarak dari titik masuk ke titik pertemuan di dalam siklus. Saat keduanya bertemu: penunjuk lambat telah menempuh F + a langkah; penunjuk cepat telah menempuh F + a + n*C langkah (lebih dahulu sebanyak n putaran penuh). Karena penunjuk cepat = 2 * penunjuk lambat: 2(F+a) = F+a+nC → F = nC - a. Ini berarti jarak dari kepala ke titik masuk sama dengan jarak dari titik pertemuan ke titik masuk (modulo C). Dengan mengembalikan salah satu penunjuk ke kepala dan memajukan keduanya sebesar 1, keduanya akan bertemu di simpul masuk.

# Verify with our example: F=1 (head to node 2), C=3 (cycle: 2->0->-4->2), a=?
# Meeting inside cycle after F+a slow steps
# Let us measure a by counting from entry to meeting point
# In practice the code handles this automatically
F = 1   # head(3) to entry(2)
C = 3   # cycle length 2->0->-4
# n=1: F = 1*C - a => a = C - F = 3 - 1 = 2
a = C - F
print(f'F={F}, C={C}, a={a}')
print(f'After meeting, {F} more steps reach entry: {F == C - a or F % C == (C - a) % C}')

Pengukuran Panjang Siklus

Setelah memperoleh titik pertemuan di dalam siklus (fase 1 algoritma Floyd), Anda dapat mengukur panjang siklus: tahan satu penunjuk tetap di tempat dan majukan penunjuk lainnya sampai keduanya bertemu lagi. Jumlah langkah yang ditempuh sama dengan panjang siklus. Hal ini berguna untuk soal yang secara khusus menanyakan panjang siklus.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def cycle_length(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:  # found meeting point
            length = 1
            fast = fast.next
            while fast is not slow:
                fast = fast.next
                length += 1
            return length
    return 0  # no cycle

nodes = [ListNode(v) for v in [1, 2, 3, 4, 5]]
for i in range(4):
    nodes[i].next = nodes[i+1]
nodes[4].next = nodes[2]  # cycle: 3->4->5->3, length=3
print(cycle_length(nodes[0]))  # 3

Bilangan Bahagia (Deteksi Siklus Tanpa Daftar)

Algoritma Floyd tidak terbatas pada daftar tertaut. LeetCode 202 'Bilangan Bahagia' menanyakan apakah penggantian n secara berulang dengan jumlah kuadrat digit-digitnya pada akhirnya mencapai 1. Jika proses tersebut memasuki siklus yang tidak mencakup 1, proses akan berulang selamanya. Anda dapat memodelkannya sebagai penelusuran daftar tertaut virtual, dengan nilai berikutnya setiap simpul berupa nilai hasil perhitungan berikutnya—lalu menerapkan algoritma Floyd untuk mendeteksi siklus.

def isHappy(n):
    def next_val(x):
        total = 0
        while x:
            x, d = divmod(x, 10)
            total += d * d
        return total

    slow, fast = n, next_val(n)
    while fast != 1 and slow != fast:
        slow = next_val(slow)
        fast = next_val(next_val(fast))
    return fast == 1

print(isHappy(19))  # True  (1->81+1=82->68->100->1)
print(isHappy(2))   # False (enters cycle)

Deteksi Berbasis Himpunan Naif vs Floyd

Pendekatan berbasis himpunan menyimpan setiap simpul yang telah dikunjungi dalam sebuah himpunan dan memeriksa keanggotaannya sebelum berkunjung. Pendekatan ini menggunakan waktu O(n) dan ruang O(n). Algoritma Floyd juga menggunakan waktu O(n), tetapi hanya ruang O(1)—tanpa struktur data tambahan. Dalam lingkungan dengan keterbatasan memori (sistem tertanam, kernel sistem operasi), jaminan ruang O(1) sangat penting. Pewawancara terkadang secara khusus meminta ruang O(1) sebagai pertanyaan lanjutan setelah Anda memberikan solusi berbasis himpunan.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# Naive O(n) space approach
def hasCycle_set(head):
    seen = set()
    while head:
        if id(head) in seen:
            return True
        seen.add(id(head))
        head = head.next
    return False

# Floyd's O(1) space approach
def hasCycle_floyd(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

print('Both implementations give the same result')

Kasus Tepi untuk Deteksi Siklus

Tiga kasus tepi perlu ditangani. Pertama, daftar kosong: head is None—kondisi perulangan Floyd fast and fast.next langsung berhenti dan menghasilkan nilai salah. Kedua, satu simpul tanpa siklus: fast.next adalah None, perulangan berhenti dan menghasilkan nilai salah. Ketiga, satu simpul dengan siklus: penunjuk berikutnya simpul menunjuk ke dirinya sendiri—penunjuk lambat dan cepat sama-sama dimulai dari kepala; setelah satu langkah, penunjuk cepat maju ke head.next.next = head, sedangkan penunjuk lambat berada di head.next = head. Kemudian keduanya sama pada iterasi pertama.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def hasCycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

# Edge cases
print(hasCycle(None))               # False: empty
node = ListNode(1)
print(hasCycle(node))               # False: single, no cycle
node.next = node
print(hasCycle(node))               # True: single node cycle

Siklus Daftar Tertaut II: LeetCode 142

LeetCode 142 'Siklus Daftar Tertaut II' meminta simpul tempat siklus dimulai (atau nilai kosong jika tidak ada siklus). Ini merupakan penerapan langsung algoritma Floyd dua fase. Pewawancara menanyakan soal ini sebagai pertanyaan lanjutan dari deteksi siklus dasar. Solusi lengkapnya: fase 1 menemukan titik pertemuan di dalam siklus; fase 2 mengembalikan salah satu penunjuk ke kepala dan menggerakkan keduanya maju sampai bertemu—titik pertemuan tersebut adalah titik masuk siklus.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def detectCycle(head):
    slow = fast = head
    # Phase 1
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            break
    else:
        return None
    # Phase 2
    ptr = head
    while ptr is not slow:
        ptr  = ptr.next
        slow = slow.next
    return ptr

nodes = [ListNode(v) for v in [1, 2, 3, 4, 5]]
for i in range(4):
    nodes[i].next = nodes[i+1]
nodes[4].next = nodes[2]  # cycle entry: node with val=3
entry = detectCycle(nodes[0])
print(entry.val)  # 3

Mengapa Floyd Mengungguli Pendekatan Himpunan

Meskipun kedua pendekatan menggunakan waktu O(n), faktor konstan dalam praktiknya berbeda. Pendekatan himpunan harus melakukan hashing pada setiap penunjuk simpul (menghitung hash, memeriksa tabel hash, dan menyimpan penunjuk), sedangkan algoritma Floyd hanya melakukan dereferensi penunjuk—jauh lebih murah untuk setiap langkah. Yang lebih penting, jaminan ruang O(1) berarti algoritma Floyd dapat berjalan pada daftar dengan panjang berapa pun tanpa risiko kehabisan memori.

Menyebutkan keunggulan ruang ini secara proaktif dalam wawancara menunjukkan pemahaman mendalam tentang pertukaran algoritmik, bukan hanya notasi Big-O.

Uji Cepat

Uji pemahaman Anda tentang konsep Struktur Data & Algoritma — Persiapan Wawancara Pemrograman dari pelajaran ini.

Ringkasan Pelajaran

Dalam pelajaran ini Anda mempelajari: algoritma penunjuk lambat-cepat Floyd mendeteksi siklus dalam waktu O(n) dan ruang O(1), fase 2 (kembalikan salah satu penunjuk ke kepala, majukan keduanya sebesar 1) menemukan simpul masuk siklus yang tepat, dan teknik yang sama berlaku di luar daftar tertaut untuk setiap urutan implisit yang memiliki fungsi 'berikutnya'. Berikutnya kita akan membahas penggabungan daftar terurut, pemisahan daftar di titik tengah, dan pencarian simpul ke-n dari akhir.

Pertanyaan yang Sering Diajukan

Apakah pelajaran “Deteksi Siklus dengan Algoritma Floyd” gratis?

Ya — teks lengkap “Deteksi Siklus dengan Algoritma Floyd” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Coding Interview Prep, upgrade ke CoddyKit PRO. Kursus Coding Interview Prep mencakup 4 pelajaran total.

Apa yang akan aku pelajari di “Deteksi Siklus dengan Algoritma Floyd”?

Deteksi siklus menggunakan pendekatan pointer lambat-cepat, temukan titik masuk siklus, dan buktikan kebenaran algoritma secara matematis. Kamu berlatih Coding Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.

Apakah aku perlu pengalaman untuk memulai Coding Interview Prep?

Tidak diperlukan pengalaman sebelumnya. Coding Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 3 dari 4.

Berapa lama pelajaran “Deteksi Siklus dengan Algoritma Floyd” memakan waktu?

Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.

Bisakah aku menulis dan menjalankan kode dalam pelajaran Coding Interview Prep ini?

Ya. Setiap pelajaran Coding Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.

Semua pelajaran dalam kursus ini

  1. Kelas Node dan Pembuatan List
  2. Membalik Linked List
  3. Deteksi Siklus dengan Algoritma Floyd
  4. Menggabungkan, Memisahkan, dan Menemukan Elemen ke-N dari Akhir
← Kembali ke Coding Interview Prep