Två pekare: långsam och snabb
Tillämpa mönstret med långsam och snabb pekare för att ta bort dubbletter in-place, flytta nollor och dela arrayer kring ett pivotvärde.
Två pekare: långsam och snabb är en gratis lektion i DSA Interview Prep på CoddyKit. Detta är lektion 4 av 4. Du kan läsa vilka 3 lektioner som helst i den här lärvägen kostnadsfritt i sin helhet – därefter låser CoddyKit PRO upp alla lektioner, plus praktisk övning med en inbyggd kodredigerare och en AI-lärare dygnet runt. Den ingår i lärvägen för DSA Interview Prep, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i DSA Interview Prep innehåller totalt 4 lektioner.
Förklaring av långsamma och snabba pekare
Mönstret med långsam och snabb pekare (även kallat sköldpaddan och haren) använder två pekare som rör sig med olika hastigheter genom samma sekvens. Till skillnad från pekare från motsatta ändar börjar båda i början. Den långsamma pekaren flyttas ett steg i taget, medan den snabba pekaren flyttas två steg (eller fler). Skillnaden i hastighet skapar användbara invariansvillkor: den långsamma pekaren håller reda på ett ”giltigt prefix”, medan den snabba pekaren söker av längre fram efter villkor.
# Slow pointer marks the write position;
# Fast pointer scans for next non-duplicate.
def remove_duplicates(nums):
if not nums: return 0
slow = 0 # next position to write a unique value
for fast in range(1, len(nums)):
if nums[fast] != nums[slow]:
slow += 1
nums[slow] = nums[fast]
return slow + 1 # new length
nums = [1, 1, 2, 3, 3, 3, 4]
k = remove_duplicates(nums)
print(nums[:k]) # [1, 2, 3, 4]Ta bort dubbletter från sorterad array
I en sorterad array ligger dubbletter intill varandra. Den långsamma pekaren håller reda på det senast skrivna unika värdet, medan den snabba pekaren söker av längre fram. När den snabba pekaren når ett värde som skiljer sig från nums[slow] flyttar ni den långsamma pekaren framåt och kopierar det nya värdet. Den här algoritmen körs på plats i O(n)-tid med O(1) extra utrymme — en vanlig intervjufråga som testar hur väl ni behärskar mönstret med läs- och skrivpekare.
def remove_duplicates_v2(nums):
slow = 0
for fast in range(len(nums)):
if nums[fast] != nums[slow]:
slow += 1
nums[slow] = nums[fast]
return slow + 1
# Allow at most 2 occurrences
def remove_duplicates_k2(nums):
slow = 0
for fast in range(len(nums)):
if slow < 2 or nums[fast] != nums[slow - 2]:
nums[slow] = nums[fast]
slow += 1
return slow
print(remove_duplicates_k2([1,1,1,2,2,3]))
# Result: 5, nums[:5] = [1,1,2,2,3]Flytta nollor med långsam och snabb pekare
Flytta alla nollor till slutet samtidigt som ni bevarar den relativa ordningen för de icke-nollställda elementen. Den långsamma pekaren markerar nästa position för ett icke-nollvärde. Den snabba pekaren söker efter icke-nollvärden. När den snabba pekaren hittar ett sådant värde kopierar ni det till den långsamma pekarens position och flyttar båda framåt. Efter sökningen fyller ni positionerna från den långsamma pekaren till slutet med nollor. O(n)-tid och O(1)-utrymme.
def move_zeroes(nums):
slow = 0 # next position for a non-zero
for fast in range(len(nums)):
if nums[fast] != 0:
nums[slow] = nums[fast]
slow += 1
# Fill rest with zeroes
while slow < len(nums):
nums[slow] = 0
slow += 1
nums = [0, 1, 0, 3, 12]
move_zeroes(nums)
print(nums) # [1, 3, 12, 0, 0]Partitionera en array kring en pivot
Partitionssteget i quicksort ordnar om elementen på plats så att alla värden < pivot kommer före värden >= pivot. Lomuto-schemat använder en långsam pekare (som markerar den sista positionen för ett litet element) och en snabb pekare (som söker framåt). När den snabba pekaren hittar ett litet element flyttar ni den långsamma pekaren framåt och byter plats på elementen. Detta körs på O(n)-tid med O(1) extra utrymme.
def lomuto_partition(nums, low, high):
pivot = nums[high]
slow = low - 1 # last position of small element
for fast in range(low, high):
if nums[fast] <= pivot:
slow += 1
nums[slow], nums[fast] = nums[fast], nums[slow]
# Place pivot in final position
nums[slow+1], nums[high] = nums[high], nums[slow+1]
return slow + 1 # pivot's final index
arr = [3, 1, 4, 1, 5, 9, 2, 6]
p = lomuto_partition(arr, 0, len(arr)-1)
print(arr) # elements before p are <= pivotHitta mitten av en länkad lista
Med långsamma och snabba pekare i en länkad lista flyttas den snabba pekaren två noder per steg, medan den långsamma pekaren flyttas en nod. När den snabba pekaren når slutet befinner sig den långsamma pekaren i mitten. Den här lösningen i ett enda genomlopp med O(n) är betydligt renare än att först räkna noderna och sedan gå halvvägs. Den används som ett delsteg i mergesort för länkade listor och vid detektering av palindrom i länkade listor.
class Node:
def __init__(self, val, nxt=None):
self.val = val
self.next = nxt
def find_middle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow # slow is at middle
# Build 1->2->3->4->5
h = Node(1, Node(2, Node(3, Node(4, Node(5)))))
mid = find_middle(h)
print(mid.val) # 3 (middle of 5 nodes)Cykeldetektering: Floyds sköldpadda och hare
Floyds cykeldetektering placerar långsamma och snabba pekare vid huvudet i en länkad lista. Den långsamma pekaren flyttas en nod och den snabba två. Om det finns en cykel kommer den snabba pekaren så småningom att hinna ikapp den långsamma, och de möts inne i cykeln. Om fast når None finns ingen cykel. Mötet är garanterat eftersom fast vinner ett steg på slow i varje iteration — i en cykel med längden k möts de inom k steg efter att slow har gått in i cykeln.
class ListNode:
def __init__(self, val=0, nxt=None):
self.val = val
self.next = nxt
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast: # identity check (same object)
return True
return False
# 1->2->3->4->2 (cycle at node 2)
n1 = ListNode(1)
n2 = ListNode(2)
n3 = ListNode(3)
n4 = ListNode(4)
n1.next=n2; n2.next=n3; n3.next=n4; n4.next=n2
print(has_cycle(n1)) # TrueHitta cykelns ingångspunkt
Efter att ni har upptäckt en cykel (slow == fast) återställer ni den ena pekaren till head. Flytta nu båda pekarna ett steg i taget. De möts vid cykelns ingångspunkt. Detta utnyttjar den matematiska egenskapen att avståndet från head till cykelns ingångspunkt är lika med avståndet från mötespunkten till cykelns ingångspunkt (modulo cykelns längd). Det här är ett elegant matematiskt resultat som ofta förekommer i svåra intervjuproblem.
def detect_cycle(head):
slow = fast = head
# Phase 1: detect
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
slow = head
while slow is not fast:
slow = slow.next
fast = fast.next
return slow # cycle entry node
# Using same cycled list as previous scene
print(detect_cycle(n1).val) # 2 (cycle entry)Långsam och snabb pekare för lyckotal
Långsamma och snabba pekare kan användas även utanför länkade listor, för alla processer som bildar cykler. Ett ”lyckotal” går genom en cykel av summor av siffrornas kvadrater — om n inte är lyckligt kommer sekvensen så småningom att gå i en loop. Upptäck loopen med slow (ett steg = en siffra i kvadrat) och fast (två steg). Om de möts vid 1 är n lyckligt; annars har det fastnat i en cykel som inte innehåller 1. Detta är Floyds algoritm tillämpad på en virtuell länkad lista av värden.
def is_happy(n):
def next_val(x):
total = 0
while x:
x, d = divmod(x, 10)
total += d * d
return total
slow = n
fast = next_val(n)
while fast != 1 and slow != fast:
slow = next_val(slow)
fast = next_val(next_val(fast))
return fast == 1
print(is_happy(19)) # True (1->9->...->1)
print(is_happy(2)) # False (enters a cycle)Den n:te noden från slutet av listan
Hitta den n:te noden från slutet av en länkad lista i ett enda genomlopp med hjälp av två pekare. Flytta den snabba pekaren n steg framåt. Flytta sedan båda pekarna tillsammans tills fast når slutet — slow befinner sig nu vid den n:te noden från slutet. Om ni vill ta bort noden behåller ni en pekare med namnet ’prev’ ett steg bakom slow. Detta är ett klassiskt problem med länkade listor som löses i ett enda genomlopp och undviker att den totala längden måste räknas först.
def remove_nth_from_end(head, n):
dummy = ListNode(0)
dummy.next = head
fast = slow = dummy
# Advance fast n+1 steps
for _ in range(n + 1):
fast = fast.next
# Advance together
while fast:
slow = slow.next
fast = fast.next
# slow.next is the nth from end
slow.next = slow.next.next
return dummy.next
# Build 1->2->3->4->5, remove 2nd from end
h2 = ListNode(1,ListNode(2,ListNode(3,ListNode(4,ListNode(5)))))
result = remove_nth_from_end(h2, 2)
# Should give 1->2->3->5Långsam och snabb pekare i strängproblem
Tänkandet med långsam och snabb pekare kan också användas i array- och strängproblem. När ni komprimerar en run-length-kodad sträng markerar den långsamma pekaren skrivpositionen, medan den snabba pekaren söker fram till slutet av varje sekvens. När alla tecken i sekvensen är lika med tecknet vid den långsamma pekaren flyttar ni fast framåt; annars registrerar ni sekvensen och uppdaterar slow. Detta ger O(n) i ett enda genomlopp med O(1) utrymme.
def compress(chars):
slow = fast = 0
while fast < len(chars):
char = chars[fast]
count = 0
# Count the run
while fast < len(chars) and chars[fast] == char:
fast += 1
count += 1
chars[slow] = char
slow += 1
if count > 1:
for c in str(count):
chars[slow] = c
slow += 1
return slow
chars = list('aabcccccaa')
print(compress(chars)) # 6
print(chars[:6]) # ['a','2','b','c','5','a']... wait
# Actually: ['a','2','b','c','5','a','2']Välja mellan långsamma och snabba pekare samt pekare från motsatta ändar
Använd pekare från motsatta ändar när problemet handlar om par med en viss målsumma, palindromkontroller eller om att pressa ihop ett fönster från båda sidor. Använd långsamma och snabba pekare när ni behöver en skrivpekare (för att ta bort eller flytta element), när ni bearbetar en länkad listas struktur (mitten, cykler) eller när ni upptäcker cykler i en värdesekvens. Båda metoderna eliminerar nästlade loopar och uppnår O(n) — den avgörande faktorn är traverseringens struktur.
# Pattern matcher:
# 1. Sorted array, target sum -> OPPOSITE ENDS
# 2. Remove/filter elements in-place -> SLOW-FAST (read-write)
# 3. Linked list middle/cycle -> SLOW-FAST (1x vs 2x speed)
# 4. Detect cycle in value sequence -> SLOW-FAST (Floyd)
# Example: given sorted array, remove val in-place
def remove_sorted(nums, val):
slow = 0
for fast in range(len(nums)):
if nums[fast] != val:
nums[slow] = nums[fast]
slow += 1
return slow
nums = [0,1,2,2,3,0,4,2]
print(remove_sorted(nums, 2)) # 5Snabbtest
Testa er förståelse av begreppen i Data Structures & Algorithms — Coding Interview Prep från den här lektionen.
Sammanfattning av lektionen
I den här lektionen lärde ni er att mönstret med långsam och snabb pekare (läs- och skrivpekare) håller en skrivpekare vid nästa giltiga position medan en snabb pekare söker framåt — grunden för borttagning, deduplicering och flytt av nollor på plats, att Floyds sköldpadda och hare upptäcker cykler i O(n)-tid och med O(1) utrymme genom att utnyttja hastighetsskillnaden mellan två pekare och att ni efter att ha upptäckt en cykel kan återställa en pekare till head och flytta båda i samma hastighet för att hitta cykelns ingångspunkt, tack vare en bevisbar avståndslikhet. Härnäst utforskar vi Pythons sträng-API inför intervjuer.
Lär dig Python 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
- 30
- Lektioner
- 120
Vanliga frågor
Är lektionen ”Två pekare: långsam och snabb” gratis?
Ja – du kan läsa vilka 3 lektioner som helst i lärvägen DSA Interview Prep, inklusive ”Två pekare: långsam och snabb”, kostnadsfritt i sin helhet här på webben. Därefter låser CoddyKit PRO upp alla lektioner, plus interaktiv övning med en inbyggd kodredigerare och en AI-lärare dygnet runt. Kursen i DSA Interview Prep innehåller totalt 4 lektioner.
Vad lär jag mig i ”Två pekare: långsam och snabb”?
Tillämpa mönstret med långsam och snabb pekare för att ta bort dubbletter in-place, flytta nollor och dela arrayer kring ett pivotvärde. Ni övar på DSA Interview Prep 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 DSA Interview Prep?
Du behöver inga förkunskaper. Utbildningen i DSA Interview Prep 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 4 av 4.
Hur lång tid tar lektionen ”Två pekare: långsam och snabb”?
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 DSA Interview Prep-lektionen?
Ja. Varje DSA Interview Prep-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
- Grunderna i arrayer och in-place-operationer
- Prefixsummor och löpande totalsummor
- Två pekare: motsatta ändar
- Två pekare: långsam och snabb