Bağlı listede döngü (cycle) olup olmadığını nasıl tespit edersiniz?

1. Hash set ile

Ziyaret edilen düğümler bir kümeye eklenir; aynı düğüme tekrar gelinirse döngü vardır. Zaman O(n), bellek O(n).

2. Floyd'un tavşan ve kaplumbağa algoritması

İki işaretçi kullanılır: slow her adımda 1, fast 2 düğüm ilerler. Döngü yoksa fast listenin sonuna (None) ulaşır. Döngü varsa fast döngü içinde slow'a her adımda 1 düğüm yaklaşır ve mutlaka yakalar.

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

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

Zaman O(n), bellek `O(1)`.

Takip sorusu: döngünün başlangıç düğümü

Buluşmadan sonra işaretçilerden biri head'e alınır; ikisi de birer adım ilerletilir. Tekrar buluştukları düğüm döngünün başlangıcıdır.

def cycle_start(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast:
            slow = head
            while slow is not fast:
                slow, fast = slow.next, fast.next
            return slow
    return None

Neden: başlangıca uzaklık a, döngü uzunluğu c ise buluşma noktasından döngü başına uzaklık da a mod c olur.

Aynı teknik "listenin ortasını bul" ve "dizide tekrar eden sayıyı bul" (LeetCode 287) sorularında da kullanılır.