PricingLoginStart free
DSA Interview Prep · Pelajaran

Pengesanan Kitaran dengan Algoritma Floyd

Kesan kitaran menggunakan pendekatan penuding perlahan-pantas, cari titik masuk kitaran dan buktikan ketepatan algoritma secara matematik.

Pelajaran 3 daripada 413 langkah

Pengesanan Kitaran dengan Algoritma Floyd ialah pelajaran DSA Interview Prep percuma di CoddyKit. Ini ialah pelajaran 3 daripada 4. Sebanyak 3 pelajaran dalam laluan pembelajaran ini boleh dibaca sepenuhnya secara percuma — selepas itu, CoddyKit PRO membuka akses kepada semua pelajaran, serta latihan praktikal dengan penyunting kod terbina dalam dan tutor kecerdasan buatan yang tersedia 24/7. Pelajaran ini merupakan sebahagian daripada laluan pembelajaran DSA Interview Prep, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus DSA Interview Prep merangkumi sejumlah 4 pelajaran.

Apakah Kitaran dalam Senarai Terpaut?

Kitaran dalam senarai terpaut berlaku apabila penuding next sesuatu nod menunjuk kembali kepada nod yang telah dilawati, lalu mewujudkan gelung tak terhingga. Melintasi senarai sedemikian dengan gelung while head akan berjalan selama-lamanya. Pengesanan kitaran ialah masalah temu duga klasik dan asas kepada algoritma penuding yang lebih maju.

Pendekatan naif menyimpan setiap nod yang telah dilawati dalam satu himpunan dan memeriksa keahlian — masa O(n), ruang O(n). Algoritma Floyd menyelesaikan masalah yang sama dalam masa O(n) dan ruang O(1), iaitu perkara yang dijangkakan oleh penemuduga.

Algoritma Penuding Perlahan-Laju Floyd

Pengesanan kitaran Floyd ('kura-kura dan arnab') menggunakan dua penuding: slow bergerak satu langkah pada satu masa, manakala fast bergerak dua langkah. Jika tiada kitaran, fast mencapai None terlebih dahulu. Jika terdapat kitaran, penuding laju akhirnya memintas penuding perlahan di dalam kitaran dan kedua-duanya bertemu pada nod yang sama. Pertemuan itu membuktikan bahawa kitaran wujud.

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 Penuding Perlahan dan Laju Sentiasa Bertemu

Secara tidak formal: setelah kedua-dua penuding memasuki kitaran, jarak antara mereka berubah sebanyak 1 bagi setiap langkah (penuding laju memperoleh 2 langkah, penuding perlahan memperoleh 1 langkah, maka jurang berkurang sebanyak 1 pada setiap pusingan). Akhirnya jurang menjadi 0 — kedua-duanya berada pada nod yang sama. Secara lebih formal, jika kitaran mempunyai panjang C, jurang maksimum di dalam kitaran ialah C-1 dan jurang berkurang sebanyak 1 pada setiap langkah, maka kedua-duanya bertemu dalam masa C langkah selepas kedua-duanya memasuki kitaran.

Jumlah langkah sebelum pertemuan: paling banyak O(n + C) = O(n) kerana 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)')

Mencari Titik Kemasukan Kitaran

Selepas mengesan kitaran, algoritma Floyd juga boleh mencari nod kemasukan (tempat kitaran bermula). Selepas slow dan fast bertemu di dalam kitaran, tetapkan semula satu penuding ke kepala dan kekalkan satu lagi pada titik pertemuan. Kemudian majukan kedua-duanya satu langkah pada satu masa. Kedua-duanya akan bertemu tepat pada nod kemasukan kitaran. Ini berfungsi kerana jarak dari kepala ke kemasukan sama dengan jarak dari titik pertemuan ke kemasukan (modulo panjang kitaran).

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

Bukti Matematik Nod Kemasukan

Ambil F = jarak dari kepala ke kemasukan kitaran, C = panjang kitaran, dan a = jarak dari kemasukan ke titik pertemuan di dalam kitaran. Apabila kedua-duanya bertemu: slow telah bergerak sejauh F + a langkah; fast telah bergerak sejauh F + a + n*C langkah (n gelung lengkap di hadapan). Oleh sebab fast = 2 * slow: 2(F+a) = F+a+nC → F = nC - a. Ini bermakna jarak dari kepala ke kemasukan sama dengan jarak dari titik pertemuan ke kemasukan (modulo C). Tetapkan semula satu penuding ke kepala dan majukan kedua-duanya sebanyak 1 langkah untuk menemukan mereka pada nod kemasukan.

# 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}')

Mengukur Panjang Kitaran

Setelah anda mempunyai titik pertemuan di dalam kitaran (fasa 1 algoritma Floyd), anda boleh mengukur panjang kitaran: kekalkan satu penuding pada kedudukannya dan majukan penuding yang satu lagi sehingga mereka bertemu semula. Bilangan langkah yang diambil sama dengan panjang kitaran. Ini berguna untuk masalah yang meminta panjang kitaran secara khusus.

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

Nombor Bahagia (Pengesanan Kitaran Tanpa Senarai)

Algoritma Floyd tidak terhad kepada senarai terpaut. LeetCode 202 'Nombor Bahagia' bertanya sama ada penggantian berulang n dengan jumlah kuasa dua digit-digitnya akhirnya mencapai 1. Jika ia memasuki kitaran yang tidak merangkumi 1, proses itu akan berulang selama-lamanya. Anda boleh memodelkannya sebagai lintasan senarai terpaut maya, dengan 'seterusnya' bagi setiap nod ialah nilai yang dikira seterusnya — kemudian gunakan algoritma Floyd untuk mengesan kitaran itu.

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)

Pengesanan Berasaskan Himpunan Naif berbanding Floyd

Pendekatan berasaskan himpunan menyimpan setiap nod yang telah dilawati dalam satu himpunan dan memeriksa keahlian sebelum melawat nod tersebut. Ia menggunakan masa O(n) dan ruang O(n). Algoritma Floyd juga menggunakan masa O(n), tetapi hanya ruang O(1) — tiada struktur data tambahan. Dalam persekitaran yang terhad dari segi memori (sistem terbenam, teras sistem pengendalian), jaminan ruang O(1) amat penting. Penemuduga kadangkala meminta ruang O(1) secara khusus sebagai soalan susulan selepas anda memberikan penyelesaian berasaskan 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')

Kes Tepi untuk Pengesanan Kitaran

Terdapat tiga kes tepi yang perlu dikendalikan. Pertama, senarai kosong: head is None — syarat gelung Floyd fast and fast.next terus keluar dan mengembalikan False. Kedua, satu nod tanpa kitaran: fast.next ialah None, gelung keluar dan mengembalikan False. Ketiga, satu nod dengan kitaran: next nod menunjuk kepada dirinya sendiri — slow dan fast kedua-duanya bermula pada head; selepas satu langkah, fast bergerak ke head.next.next = head, manakala slow berada pada head.next = head. Kemudian fast == slow pada lelaran 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

Kitaran Senarai Terpaut II: LeetCode 142

LeetCode 142 'Kitaran Senarai Terpaut II' meminta nod tempat kitaran bermula (atau None jika tiada kitaran). Ini ialah penerapan langsung algoritma Floyd dua fasa. Penemuduga bertanya soalan ini sebagai susulan kepada pengesanan kitaran asas. Penyelesaian lengkap: fasa 1 mencari titik pertemuan di dalam kitaran; fasa 2 menetapkan semula satu penuding ke kepala dan menggerakkan kedua-duanya ke hadapan sehingga bertemu — titik pertemuan itu ialah kemasukan kitaran.

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 Mengatasi Pendekatan Himpunan

Walaupun kedua-dua pendekatan menggunakan masa O(n), faktor pemalar berbeza dalam amalan. Pendekatan himpunan perlu mencincang setiap penuding nod (mengira cincangan, mencari dalam jadual cincang, dan menyimpan penuding), manakala algoritma Floyd hanya melakukan penyahrujukan penuding — jauh lebih murah bagi setiap langkah. Lebih penting lagi, jaminan ruang O(1) bermakna algoritma Floyd boleh dijalankan pada senarai yang panjangnya sewenang-wenangnya tanpa risiko kehabisan memori.

Menyebut kelebihan ruang ini secara proaktif dalam temu duga menunjukkan pemahaman mendalam tentang pertukaran algoritma yang melangkaui tatatanda Big-O semata-mata.

Semakan Pantas

Uji pemahaman anda tentang konsep Struktur Data & Algoritma — Persediaan Temu Duga Pengekodan daripada pelajaran ini.

Jawab dalam pelajaran interaktif

Ulang Kaji Pelajaran

Dalam pelajaran ini anda telah mempelajari: algoritma penuding perlahan-laju Floyd mengesan kitaran dalam masa O(n) dan ruang O(1), fasa 2 (tetapkan semula satu penuding ke kepala dan majukan kedua-duanya sebanyak 1) mencari nod kemasukan kitaran yang tepat, dan teknik yang sama boleh digunakan di luar senarai terpaut untuk sebarang jujukan tersirat yang 'seterusnya' ialah suatu fungsi. Seterusnya, kita akan membincangkan penggabungan senarai terisih, pemisahan senarai pada titik tengah, dan pencarian nod ke-n dari hujung.

Percuma untuk bermula

Pelajari Python dengan tutor kecerdasan buatan — percuma

Tulis dan jalankan kod sebenar dalam pelayar anda, dapatkan bantuan segera daripada tutor kecerdasan buatan yang tersedia 24/7, dan sambung semula dari tempat anda berhenti di web atau dalam aplikasi.

Kursus
30
Pelajaran
120
Mula belajar secara percumaLihat kursus penuh

Soalan Lazim

Adakah pelajaran “Pengesanan Kitaran dengan Algoritma Floyd” percuma?

Ya — sebanyak 3 pelajaran dalam laluan pembelajaran DSA Interview Prep, termasuk “Pengesanan Kitaran dengan Algoritma Floyd”, boleh dibaca sepenuhnya secara percuma di web ini. Selepas itu, CoddyKit PRO membuka akses kepada semua pelajaran, serta latihan interaktif dengan penyunting kod terbina dalam dan tutor kecerdasan buatan yang tersedia 24/7. Kursus DSA Interview Prep merangkumi sejumlah 4 pelajaran.

Apakah yang akan saya pelajari dalam “Pengesanan Kitaran dengan Algoritma Floyd”?

Kesan kitaran menggunakan pendekatan penuding perlahan-pantas, cari titik masuk kitaran dan buktikan ketepatan algoritma secara matematik. Anda berlatih DSA Interview Prep menggunakan kod praktikal yang dijalankan terus dalam pelayar, manakala tutor kecerdasan buatan 24/7 menjawab soalan anda semasa anda mengikuti pelajaran.

Adakah saya memerlukan pengalaman untuk memulakan DSA Interview Prep?

Tiada pengalaman terdahulu diperlukan. Pembelajaran DSA Interview Prep di CoddyKit disusun untuk pelajar daripada peringkat pemula hingga lanjutan, jadi anda boleh bermula di sini atau dari awal dan belajar mengikut kadar anda sendiri. Ini ialah pelajaran 3 daripada 4.

Berapa lamakah pelajaran “Pengesanan Kitaran dengan Algoritma Floyd” diambil?

Kebanyakan pelajaran CoddyKit mengambil masa kira-kira 5–10 minit. Setiap pelajaran ringkas dan interaktif, jadi anda boleh membuat kemajuan secara berterusan dan menyambung tepat dari tempat anda berhenti di web atau aplikasi.

Bolehkah saya menulis dan menjalankan kod dalam pelajaran DSA Interview Prep ini?

Ya. Setiap pelajaran DSA Interview Prep menyertakan penyunting kod terbina dalam, jadi anda boleh menulis dan menjalankan kod sebenar terus dalam pelayar serta menerima maklum balas kecerdasan buatan serta-merta — tanpa memerlukan persediaan setempat.

Semua pelajaran dalam kursus ini

  1. Kelas Nod dan Pembinaan Senarai
  2. Membalikkan Senarai Berantai
  3. Pengesanan Kitaran dengan Algoritma Floyd
  4. Menggabung, Memisah dan Mencari Nod ke-N dari Hujung
← Kembali ke DSA Interview Prep