0Pricing
DSA Interview Prep · Lekcja

Wykrywanie cyklu algorytmem Floyda

Wykryją Państwo cykle za pomocą podejścia wolnego i szybkiego wskaźnika, znajdą punkt wejścia do cyklu i matematycznie uzasadnią poprawność algorytmu.

Wykrywanie cyklu algorytmem Floyda to bezpłatna lekcja DSA Interview Prep na CoddyKit. To lekcja 3 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej DSA Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.

Czym jest cykl w liście wiązanej?

Cykl w liście wiązanej występuje, gdy wskaźnik next węzła wskazuje na wcześniej odwiedzony węzeł, tworząc nieskończoną pętlę. Przechodzenie przez taką listę za pomocą pętli while head trwałoby bez końca. Wykrywanie cykli to klasyczny problem rekrutacyjny i podstawa bardziej zaawansowanych algorytmów wykorzystujących wskaźniki.

Naive podejście przechowuje każdy odwiedzony węzeł w zbiorze i sprawdza jego obecność — czas O(n), pamięć O(n). Algorytm Floyda rozwiązuje ten sam problem w czasie O(n) i przy użyciu O(1) pamięci, czego oczekują osoby prowadzące rozmowy rekrutacyjne.

Algorytm wolnego i szybkiego wskaźnika Floyda

Algorytm wykrywania cykli Floyda („żółw i zając”) używa dwóch wskaźników: slow przesuwa się o jeden krok naraz, a fast o dwa kroki. Jeśli cykl nie istnieje, fast jako pierwszy dociera do None. Jeśli cykl istnieje, fast w końcu dogania slow wewnątrz cyklu i oba wskaźniki spotykają się w tym samym węźle. To spotkanie dowodzi istnienia cyklu.

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

Dlaczego wolny i szybki wskaźnik zawsze się spotykają

W ujęciu intuicyjnym: gdy oba wskaźniki znajdą się w cyklu, odległość między nimi zmienia się o 1 w każdym kroku (fast zyskuje 2, slow zyskuje 1, więc różnica zmniejsza się o 1 w każdej rundzie). W końcu różnica wynosi 0 — wskaźniki znajdują się w tym samym węźle. Formalnie, jeśli cykl ma długość C, największa różnica wewnątrz cyklu wynosi C-1, a różnica zmniejsza się o 1 w każdym kroku, więc wskaźniki spotkają się w ciągu C kroków od chwili, gdy oba znajdą się w cyklu.

Łączna liczba kroków przed spotkaniem: co najwyżej O(n + C) = O(n), ponieważ 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)')

Znajdowanie punktu wejścia do cyklu

Po wykryciu cyklu algorytm Floyda może również znaleźć węzeł wejściowy (miejsce rozpoczęcia cyklu). Gdy slow i fast spotkają się wewnątrz cyklu, należy przestawić jeden wskaźnik na head, a drugi pozostawić w punkcie spotkania. Następnie oba wskaźniki należy przesuwać po jednym kroku. Spotkają się dokładnie w węźle wejściowym cyklu. Dzieje się tak, ponieważ odległość od head do punktu wejścia jest równa odległości od punktu spotkania do punktu wejścia (modulo długość cyklu).

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

Matematyczny dowód węzła wejściowego

Niech F = odległość od head do punktu wejścia cyklu, C = długość cyklu, a a = odległość od punktu wejścia do punktu spotkania wewnątrz cyklu. W chwili spotkania slow przebył F + a kroków, a fast przebył F + a + n*C kroków (o n pełnych okrążeń więcej). Ponieważ fast = 2 * slow: 2(F+a) = F+a+nC → F = nC - a. Oznacza to, że odległość od head do punktu wejścia jest równa odległości od punktu spotkania do punktu wejścia (modulo C). Po przestawieniu jednego wskaźnika na head i przesuwaniu obu o 1 wskaźniki zbiegną się w węźle wejściowym.

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

Pomiar długości cyklu

Po znalezieniu punktu spotkania wewnątrz cyklu (faza 1 algorytmu Floyda) można także zmierzyć długość cyklu: jeden wskaźnik należy pozostawić nieruchomy, a drugi przesuwać aż do ponownego spotkania. Liczba wykonanych kroków jest równa długości cyklu. Jest to przydatne w zadaniach, które wymagają jawnego wyznaczenia długości cyklu.

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

Szczęśliwa liczba (wykrywanie cyklu bez listy)

Algorytm Floyda nie ogranicza się do list wiązanych. LeetCode 202 „Happy Number” wymaga sprawdzenia, czy wielokrotne zastępowanie n sumą kwadratów jego cyfr doprowadzi ostatecznie do 1. Jeśli wartość wejdzie w cykl, który nie zawiera 1, obliczenia będą powtarzać się bez końca. Można zamodelować to jako przechodzenie po wirtualnej liście wiązanej, w której wartością 'next' każdego węzła jest kolejna obliczona wartość — a następnie zastosować algorytm Floyda do wykrycia cyklu.

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)

Naiwne wykrywanie oparte na zbiorze a algorytm Floyda

Podejście oparte na zbiorze przechowuje każdy odwiedzony węzeł w zbiorze i sprawdza jego obecność przed odwiedzeniem. Ma złożoność czasową O(n) i pamięciową O(n). Algorytm Floyda również działa w czasie O(n), ale używa tylko O(1) pamięci — nie wymaga dodatkowej struktury danych. W środowiskach o ograniczonej pamięci (systemach wbudowanych, jądrach systemów operacyjnych) gwarancja O(1) pamięci ma znaczenie. Osoby prowadzące rozmowy rekrutacyjne czasami wyraźnie wymagają O(1) pamięci jako dodatkowego pytania po przedstawieniu rozwiązania opartego na zbiorze.

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

Przypadki brzegowe wykrywania cykli

Należy obsłużyć trzy przypadki brzegowe. Po pierwsze, pusta lista: head is None — warunek pętli algorytmu Floyda fast and fast.next natychmiast kończy działanie i zwraca False. Po drugie, pojedynczy węzeł bez cyklu: fast.next ma wartość None, więc pętla się kończy i zwraca False. Po trzecie, pojedynczy węzeł z cyklem: wskaźnik next węzła wskazuje na niego samego — slow i fast zaczynają w head; po jednym kroku fast przesuwa się do head.next.next = head, a slow znajduje się w head.next = head. Następnie fast == slow już w pierwszej iteracji.

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

Cykl w liście wiązanej II: LeetCode 142

LeetCode 142 „Linked List Cycle II” wymaga wskazania węzła, w którym zaczyna się cykl (lub None, jeśli cykl nie istnieje). Jest to bezpośrednie zastosowanie dwuetapowego algorytmu Floyda. Osoby prowadzące rozmowy rekrutacyjne zadają to pytanie jako rozwinięcie podstawowego wykrywania cyklu. Pełne rozwiązanie: faza 1 znajduje punkt spotkania wewnątrz cyklu; faza 2 przestawia jeden wskaźnik na head i przesuwa oba do przodu, aż się spotkają — ten punkt spotkania jest punktem wejścia do cyklu.

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

Dlaczego algorytm Floyda jest lepszy od podejścia opartego na zbiorze

Choć oba podejścia mają złożoność czasową O(n), w praktyce różni je stały współczynnik. Podejście oparte na zbiorze musi haszować wskaźnik każdego węzła (obliczyć hash, przeszukać tablicę mieszającą i przechować wskaźnik), podczas gdy algorytm Floyda wykonuje tylko dereferencje wskaźników — znacznie tańsze operacje w każdym kroku. Co ważniejsze, gwarancja O(1) pamięci oznacza, że algorytm Floyda może działać na dowolnie długich listach bez ryzyka wyczerpania pamięci.

Samodzielne wskazanie tej zalety pamięciowej podczas rozmowy rekrutacyjnej sygnalizuje głębokie zrozumienie kompromisów algorytmicznych wykraczające poza same oznaczenia Big-O.

Szybkie sprawdzenie

Sprawdź, czy rozumiesz pojęcia z kursu Data Structures & Algorithms — Coding Interview Prep omówione w tej lekcji.

Podsumowanie lekcji

W tej lekcji omówiono: algorytm wolnego i szybkiego wskaźnika Floyda wykrywa cykle w czasie O(n) i przy użyciu O(1) pamięci, faza 2 (przestawienie jednego wskaźnika na head i przesuwanie obu o 1) znajduje dokładny węzeł wejściowy cyklu oraz ta sama technika działa nie tylko dla list wiązanych, ale dla każdej niejawnej sekwencji, w której 'next' jest funkcją. Następnie omówimy scalanie posortowanych list, dzielenie list w punktach środkowych i znajdowanie n-tego węzła od końca.

Często zadawane pytania

Czy lekcja „Wykrywanie cyklu algorytmem Floyda” jest bezpłatna?

Tak — pełny tekst „Wykrywanie cyklu algorytmem Floyda” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu DSA Interview Prep, przejdź na CoddyKit PRO. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.

Co nauczysz się w „Wykrywanie cyklu algorytmem Floyda”?

Wykryją Państwo cykle za pomocą podejścia wolnego i szybkiego wskaźnika, znajdą punkt wejścia do cyklu i matematycznie uzasadnią poprawność algorytmu. Ćwiczysz DSA Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.

Czy potrzebuję doświadczenia, aby zacząć DSA Interview Prep?

Nie wymagamy żadnego doświadczenia. DSA Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 3 z 4.

Ile czasu zajmuje lekcja „Wykrywanie cyklu algorytmem Floyda”?

Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.

Czy mogę pisać i uruchamiać kod w tej lekcji DSA Interview Prep?

Tak. Każda lekcja DSA Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.

Wszystkie lekcje w tym kursie

  1. Klasa Node i tworzenie listy
  2. Odwracanie listy jednokierunkowej
  3. Wykrywanie cyklu algorytmem Floyda
  4. Scalanie, dzielenie i znajdowanie n-tego elementu od końca
← Powrót do DSA Interview Prep