DSA Interview Prep · Ders

Floyd Algoritmasıyla Döngü Algılama

Q: “Floyd Algoritmasıyla Döngü Algılama” dersi ücretsiz mi?

Evet — “Floyd Algoritmasıyla Döngü Algılama” dersin tüm metni burada web'de ücretsiz olarak okunabilir. Etkileşimli olarak pratik yapmak (yerleşik kod editörü ve 7/24 yapay zeka koçu) ve DSA Interview Prep kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. DSA Interview Prep kursu toplamda 4 dersten oluşur.

Q: DSA Interview Prep öğrenmeye başlamak için deneyim gerekli mi?

Önceden deneyim gerekmez. CoddyKit'te DSA Interview Prep, başlangıçtan ileri seviyeye kadar yapılandırıldığı için buradan başlayabilir veya başından başlayıp kendi hızında ilerleme yapabilirsin. Bu, 4 dersinin 3. dersidir.

Q: “Floyd Algoritmasıyla Döngü Algılama” dersi ne kadar sürer?

Çoğu CoddyKit dersi yaklaşık 5–10 dakika sürer. Her biri kısa ve etkileşimli olduğu için sabit ilerleme yaparsın ve web ile uygulama arasında tam olarak bıraktığın yerden devam edebilirsin.

Q: Bu DSA Interview Prep dersinde kod yazıp çalıştırabilir miyim?

Evet. Her DSA Interview Prep dersi yerleşik bir kod editörü içerir, bu sayede tarayıcıda gerçek kod yazıp çalıştırabilir ve anlık yapay zeka geri bildirimi alırsın — yerel kurulum gerekli değildir.

Yavaş-hızlı işaretçi yaklaşımıyla döngüleri algılayın, döngünün giriş noktasını bulun ve algoritmanın doğruluğunu matematiksel olarak kanıtlayın.

Floyd Algoritmasıyla Döngü Algılama, CoddyKit'te ücretsiz bir DSA Interview Prep dersidir. Bu, 4 dersinin 3. dersidir. Aşağıdan dersin tamamını ücretsiz okuyabilir, sonra tarayıcıda yerleşik kod editörü ve 7/24 yapay zeka koçu ile uygulamalı olarak pratik yapabilirsin. Bu, DSA Interview Prep öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. DSA Interview Prep kursu toplamda 4 dersten oluşur.

Bağlı Listede Döngü Nedir

Bağlı listede döngü, bir düğümün next işaretçisinin daha önce ziyaret edilmiş bir düğüme geri dönerek sonsuz bir döngü oluşturmasıyla meydana gelir. Böyle bir listeyi while head döngüsüyle dolaşmak işlemin sonsuza kadar sürmesine neden olur. Döngü algılama, klasik bir mülakat problemidir ve daha ileri düzey işaretçi algoritmalarının temelini oluşturur.

Saf yaklaşım, ziyaret edilen her düğümü bir kümede saklayıp üyeliğini kontrol eder; zaman karmaşıklığı O(n), bellek alanı karmaşıklığı O(n)'dir. Floyd algoritması aynı problemi O(n) zamanda ve O(1) bellek alanında çözer; mülakatçıların beklediği de budur.

Floyd'un Yavaş-Hızlı İşaretçi Algoritması

Floyd'un döngü algılama algoritması, yani 'kaplumbağa ve tavşan' yöntemi, iki işaretçi kullanır: slow her seferinde bir adım, fast ise iki adım ilerler. Döngü yoksa fast önce None değerine ulaşır. Döngü varsa hızlı işaretçi sonunda döngünün içinde yavaş işaretçiyi yakalar ve ikisi aynı düğümde buluşur. Bu buluşma, bir döngünün varlığını kanıtlar.

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

Yavaş ve Hızlı İşaretçiler Neden Her Zaman Buluşur

Sezgisel olarak: her iki işaretçi de döngüye girdikten sonra aralarındaki mesafe her adımda 1 değişir (hızlı işaretçi 2, yavaş işaretçi 1 adım ilerlediğinden aradaki fark her turda 1 azalır). Sonunda fark 0 olur; yani ikisi aynı düğümde bulunur. Daha biçimsel olarak, döngünün uzunluğu C ise döngü içindeki en büyük fark C-1'dir ve fark her adımda 1 azaldığından, her iki işaretçi döngüye girdikten sonra en geç C adım içinde buluşurlar.

Buluşmadan önceki toplam adım sayısı: C <= n olduğundan en fazla O(n + C) = O(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)')

Döngünün Giriş Noktasını Bulma

Bir döngü algılandıktan sonra Floyd algoritması giriş düğümünü, yani döngünün başladığı yeri de bulabilir. Yavaş ve hızlı işaretçiler döngünün içinde buluştuktan sonra bir işaretçiyi başa sıfırlayın, diğerini ise buluşma noktasında bırakın. Ardından ikisini de her seferinde bir adım ilerletin. Tam olarak döngünün giriş düğümünde buluşacaklardır. Bunun nedeni, baştan girişe olan mesafenin buluşma noktasından girişe olan mesafeye döngü uzunluğuna göre eşit olmasıdır.

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

Giriş Düğümünün Matematiksel Kanıtı

F = baştan döngü girişine olan mesafe, C = döngü uzunluğu ve a = döngü içinde girişten buluşma noktasına olan mesafe olsun. Buluştuklarında: yavaş işaretçi F + a adım ilerlemiştir; hızlı işaretçi ise F + a + n*C adım ilerlemiştir (n tam tur öndedir). Hızlı işaretçi = 2 * yavaş işaretçi olduğundan: 2(F+a) = F+a+nC → F = nC - a. Bu, baştan girişe olan mesafenin buluşma noktasından girişe olan mesafeye C'ye göre eşit olduğunu gösterir. Bir işaretçiyi başa sıfırlayıp ikisini de 1'er adım ilerletmek, onları giriş düğümünde buluşturur.

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

Döngü Uzunluğunu Ölçme

Döngünün içindeki buluşma noktasını (Floyd algoritmasının 1. aşamasında) elde ettikten sonra döngü uzunluğunu ölçebilirsiniz: bir işaretçiyi sabit tutun ve diğerini yeniden buluşana kadar ilerletin. Atılan adım sayısı döngü uzunluğuna eşittir. Bu, döngü uzunluğunu açıkça soran problemler için kullanışlıdır.

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

Mutlu Sayı (Liste Kullanmadan Döngü Algılama)

Floyd algoritması yalnızca bağlı listelerle sınırlı değildir. LeetCode 202, 'Mutlu Sayı', n sayısını basamaklarının kareleri toplamıyla art arda değiştirmenin sonunda 1'e ulaşılıp ulaşılmadığını sorar. Sonuç 1'i içermeyen bir döngüye girerse işlem sonsuza kadar sürer. Bunu, her düğümün 'next' değerinin bir sonraki hesaplanan değer olduğu sanal bir bağlı liste dolaşımı olarak modelleyebilir ve ardından döngüyü algılamak için Floyd algoritmasını uygulayabilirsiniz.

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)

Naif Küme Tabanlı Algılama ve Floyd Algoritması

Küme tabanlı yaklaşım, ziyaret edilen her düğümü bir kümede saklar ve ziyaret etmeden önce üyeliğini kontrol eder. Zaman karmaşıklığı O(n), bellek alanı karmaşıklığı O(n)'dir. Floyd algoritması da O(n) zamanda çalışır, ancak yalnızca O(1) bellek alanı kullanır; ek bir veri yapısına ihtiyaç duymaz. Bellek açısından kısıtlı ortamlarda (gömülü sistemler ve işletim sistemi çekirdekleri) O(1) bellek alanı garantisi önemlidir. Mülakatçılar, küme çözümünü sunduktan sonra bazen özellikle O(1) bellek alanı kullanılmasını ek soru olarak ister.

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

Döngü Algılamada Sınır Durumları

Ele alınması gereken üç sınır durumu vardır. İlk olarak, boş liste: head is None durumunda Floyd algoritmasının fast and fast.next döngü koşulu hemen sona erer ve False döndürülür. İkinci olarak, döngüsü olmayan tek düğüm: fast.next None'dur, döngü sona erer ve False döndürülür. Üçüncü olarak, döngüsü olan tek düğüm: düğümün next işaretçisi kendisini gösterir; yavaş ve hızlı işaretçiler baştan başlar. Bir adım sonra fast, head.next.next = head ile başa ilerler; slow ise head.next = head konumundadır. Böylece ilk yinelemede fast == slow olur.

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

Bağlı Liste Döngüsü II: LeetCode 142

LeetCode 142, 'Bağlı Liste Döngüsü II', döngünün başladığı düğümü (veya döngü yoksa None değerini) bulmanızı ister. Bu, Floyd algoritmasının iki aşamalı biçiminin doğrudan uygulanmasıdır. Mülakatçılar bunu temel döngü algılama sorusunun devamı olarak sorar. Tam çözüm şöyledir: 1. aşama döngünün içindeki buluşma noktasını bulur; 2. aşama bir işaretçiyi başa sıfırlar ve ikisini de buluşana kadar ileri yürütür; bu buluşma noktası döngünün girişidir.

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

Floyd Algoritması Neden Küme Yaklaşımından Üstündür

Her iki yaklaşımın da zaman karmaşıklığı O(n) olsa da pratikte sabit katsayıları farklıdır. Küme yaklaşımı her düğüm işaretçisini karma değerine dönüştürmek (karma değerini hesaplamak, karma tablosunda arama yapmak ve işaretçiyi saklamak) zorundadır; Floyd algoritması ise yalnızca işaretçi çözümlemeleri gerçekleştirir ve adım başına çok daha az maliyetlidir. Daha da önemlisi, O(1) bellek alanı garantisi Floyd algoritmasının bellek tükenmesi riski olmadan rastgele uzunluktaki listelerde çalışabilmesini sağlar.

Bir mülakatta bu bellek avantajından kendiliğinizden söz etmeniz, ham Büyük O gösteriminin ötesindeki algoritmik ödünleşimleri derinlemesine anladığınızı gösterir.

Hızlı Kontrol

Bu derste ele alınan Veri Yapıları ve Algoritmalar — Kodlama Mülakatına Hazırlık kavramlarını ne kadar anladığınızı sınayın.

Ders Özeti

Bu derste şunları öğrendiniz: Floyd'un yavaş-hızlı işaretçi algoritması döngüleri O(n) zamanda ve O(1) bellek alanında algılar, 2. aşama (bir işaretçiyi başa sıfırlayıp ikisini de 1'er adım ilerletmek) döngünün tam giriş düğümünü bulur ve aynı teknik, bağlı listelerin ötesinde, sonraki değerin bir işlevle belirlendiği her örtük diziye uygulanabilir. Sırada sıralı listeleri birleştirmeyi, listeleri orta noktalarından bölmeyi ve sondan n'inci düğümü bulmayı ele alacağız.

Sıkça Sorulan Sorular