Cykeldetektering med Floyds algoritm
Detektera cykler med metoden med långsam och snabb pekare, hitta cykelns startpunkt och bevisa algoritmens korrekthet matematiskt.
Cykeldetektering med Floyds algoritm är en gratis lektion i Förberedelse inför kodningsintervjuer på CoddyKit. Detta är lektion 3 av 4. Ni kan läsa hela lektionen gratis nedan och sedan öva praktiskt i webbläsaren med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt. Den ingår i lärvägen för Förberedelse inför kodningsintervjuer, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.
Vad är en cykel i en länkad lista?
En cykel i en länkad lista uppstår när en nods next-pekare pekar tillbaka på en tidigare besökt nod och skapar en oändlig loop. Att traversera en sådan lista med en while head-loop skulle fortsätta för evigt. Cykeldetektering är ett klassiskt intervjuproblem och grunden för mer avancerade pekaralgoritmer.
Det naiva tillvägagångssättet lagrar varje besökt nod i en mängd och kontrollerar om den finns där — O(n) tid och O(n) utrymme. Floyds algoritm löser samma problem på O(n) tid och med O(1) utrymme, vilket är vad intervjuare förväntar sig.
Floyds algoritm med långsam och snabb pekare
Floyds cykeldetektering (”sköldpaddan och haren”) använder två pekare: slow avancerar ett steg i taget och fast avancerar två steg. Om det inte finns någon cykel når fast None först. Om det finns en cykel kommer fast så småningom ikapp slow inne i cykeln, och de möts vid samma nod. Mötet bevisar att det finns en cykel.
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])) # TrueVarför den långsamma och den snabba pekaren alltid möts
Informellt: när båda pekarna har gått in i cykeln ändras avståndet mellan dem med 1 per steg (fast avancerar 2 steg och slow 1, så avståndet minskar med 1 varje omgång). Mer formellt: om cykeln har längden C är det största avståndet inne i cykeln C-1, och avståndet minskar med 1 varje steg. Därför möts de inom C steg efter att båda har gått in i cykeln.
Det totala antalet steg före mötet är högst O(n + C) = O(n), eftersom 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)')Hitta cykelns startnod
Efter att ha upptäckt en cykel kan Floyds algoritm också hitta startnoden (där cykeln börjar). När slow och fast har mötts inne i cykeln återställer du den ena pekaren till head och låter den andra vara kvar vid mötespunkten. Flytta sedan båda framåt ett steg i taget. De möts exakt vid cykelns startnod. Detta fungerar eftersom avståndet från head till startnoden är lika med avståndet från mötespunkten till startnoden (modulo cykellängden).
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) # 2Matematiskt bevis för cykelns startnod
Låt F = avståndet från head till cykelns startnod, C = cykelns längd och a = avståndet från startnoden till mötespunkten inne i cykeln. När de möts har slow gått F + a steg och fast har gått F + a + n*C steg (n kompletta varv före). Eftersom fast = 2 * slow gäller: 2(F+a) = F+a+nC → F = nC - a. Detta innebär att avståndet från head till startnoden är lika med avståndet från mötespunkten till startnoden (modulo C). Om du återställer den ena pekaren till head och flyttar båda ett steg i taget möts de vid startnoden.
# 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}')Mätning av cykellängd
När du har mötespunkten inne i cykeln (fas 1 i Floyds algoritm) kan du mäta cykellängden: håll den ena pekaren stilla och flytta den andra tills de möts igen. Antalet steg är lika med cykellängden. Detta är användbart i problem där cykellängden efterfrågas uttryckligen.
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])) # 3Happy Number (cykeldetektering utan lista)
Floyds algoritm är inte begränsad till länkade listor. LeetCode 202 'Happy Number' frågar om n genom att upprepade gånger ersättas med summan av kvadraterna av sina siffror så småningom når 1. Om det hamnar i en cykel som inte innehåller 1 kommer det att loopa för evigt. Detta kan modelleras som traversering av en virtuell länkad lista där varje nods 'next' är nästa beräknade värde — tillämpa sedan Floyds algoritm för att upptäcka cykeln.
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)Naiv mängdbaserad detektering jämfört med Floyds metod
Den mängdbaserade metoden lagrar varje besökt nod i en mängd och kontrollerar om den finns där innan den besöks. Den har tidskomplexiteten O(n) och utrymmeskomplexiteten O(n). Floyds metod har också O(n) tid, men bara O(1) utrymme — ingen extra datastruktur behövs. I minnesbegränsade miljöer, till exempel inbyggda system och operativsystemkärnor, är garantin om O(1) utrymme viktig. Intervjuare ber ibland uttryckligen om O(1) utrymme som en följdfråga efter att du har presenterat mängdlösningen.
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')Specialfall vid cykeldetektering
Tre specialfall måste hanteras. För det första, tom lista: head is None — Floyds loopvillkor fast and fast.next avslutas omedelbart och returnerar False. För det andra, en enda nod utan cykel: fast.next är None, loopen avslutas och False returneras. För det tredje, en enda nod med cykel: nodens next pekar på den själv — slow och fast startar båda vid head. Efter ett steg flyttas fast till head.next.next = head, medan slow befinner sig vid head.next = head. Därefter är fast == slow redan vid den första iterationen.
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 cycleLinked List Cycle II: LeetCode 142
LeetCode 142 'Linked List Cycle II' frågar efter noden där cykeln börjar (eller None om ingen cykel finns). Detta är en direkt tillämpning av Floyds algoritm i två faser. Intervjuare ställer ofta denna fråga som en följdfråga efter den grundläggande cykeldetekteringen. Den fullständiga lösningen är: fas 1 hittar mötespunkten inne i cykeln; fas 2 återställer den ena pekaren till head och flyttar båda framåt tills de möts — mötespunkten är cykelns startnod.
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) # 3Varför Floyds metod slår mängdmetoden
Även om båda metoderna har O(n) tid skiljer sig den konstanta faktorn i praktiken. Mängdmetoden måste hasha varje nodpekare (beräkna hashvärdet, söka i hashtabellen och lagra pekaren), medan Floyds metod endast utför avreferenseringar av pekare — mycket billigare per steg. Ännu viktigare är garantin om O(1) utrymme, som innebär att Floyds metod kan köras på godtyckligt långa listor utan risk för att minnet tar slut.
Om du självmant nämner denna utrymmesfördel vid en intervju visar det att du har en djup förståelse för algoritmiska avvägningar bortom den grundläggande Big-O-notationen.
Snabbkontroll
Kontrollera dina kunskaper om begreppen från Data Structures & Algorithms — Coding Interview Prep i den här lektionen.
Sammanfattning av lektionen
I den här lektionen lärde du dig: Floyds algoritm med långsam och snabb pekare upptäcker cykler på O(n) tid och med O(1) utrymme, fas 2 (återställ den ena pekaren till head och flytta båda med 1) hittar cykelns exakta startnod och samma teknik kan användas utanför länkade listor för alla implicita sekvenser där 'next' är en funktion. Nästa del handlar om att slå ihop sorterade listor, dela listor vid mittpunkter och hitta den n:te noden från slutet.
Lär dig Förberedelse inför kodningsintervjuer med en AI-lärare – gratis
Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.
- Kurser
- 90
- Lektioner
- 360
Vanliga frågor
Är lektionen ”Cykeldetektering med Floyds algoritm” gratis?
Ja – hela texten till ”Cykeldetektering med Floyds algoritm” kan läsas gratis här på webben. Om Ni vill öva interaktivt med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt och låsa upp resten av kursen i Förberedelse inför kodningsintervjuer, kan Ni uppgradera till CoddyKit PRO. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.
Vad lär jag mig i ”Cykeldetektering med Floyds algoritm”?
Detektera cykler med metoden med långsam och snabb pekare, hitta cykelns startpunkt och bevisa algoritmens korrekthet matematiskt. Ni övar på Förberedelse inför kodningsintervjuer med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.
Behöver jag någon erfarenhet för att börja lära mig Förberedelse inför kodningsintervjuer?
Du behöver inga förkunskaper. Utbildningen i Förberedelse inför kodningsintervjuer på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 3 av 4.
Hur lång tid tar lektionen ”Cykeldetektering med Floyds algoritm”?
De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.
Kan jag skriva och köra kod i den här Förberedelse inför kodningsintervjuer-lektionen?
Ja. Varje Förberedelse inför kodningsintervjuer-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.
Alla lektioner i den här kursen
- Node-klassen och listkonstruktion
- Vända en länkad lista
- Cykeldetektering med Floyds algoritm
- Sammanfoga, dela och hitta den n:te från slutet