Zwei Zeiger: langsam und schnell
Wenden Sie das Muster mit langsamem und schnellem Zeiger an, um Duplikate In-Place zu entfernen, Nullen zu verschieben und Arrays um einen Pivot-Wert zu partitionieren.
Zwei Zeiger: langsam und schnell ist eine kostenlose DSA Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 4 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des DSA Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der DSA Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Langsame und schnelle Zeiger erklärt
Das Muster mit langsamen und schnellen Zeigern (auch Tortoise-and-Hare genannt) verwendet zwei Zeiger, die sich mit unterschiedlicher Geschwindigkeit durch dieselbe Sequenz bewegen. Anders als Zeiger an entgegengesetzten Enden beginnen beide am Anfang. Der langsame Zeiger geht jeweils einen Schritt weiter, der schnelle zwei oder mehr. Der Geschwindigkeitsunterschied erzeugt nützliche Invarianten: Der langsame Zeiger verfolgt ein „gültiges Präfix“, während der schnelle Zeiger vorausläuft und nach bestimmten Bedingungen sucht.
# 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]Duplikate aus sortiertem Array entfernen
In einem sortierten Array stehen Duplikate nebeneinander. Der langsame Zeiger verfolgt den zuletzt geschriebenen eindeutigen Wert, während der schnelle Zeiger vorausläuft. Sobald der schnelle Zeiger einen Wert erreicht, der sich von nums[slow] unterscheidet, bewegen Sie slow weiter und kopieren den neuen Wert. Dieser In-Place-Algorithmus läuft in O(n) Zeit und benötigt O(1) zusätzlichen Speicher — eine typische Interviewaufgabe, die die Beherrschung des Lese-Schreib-Zeiger-Musters prüft.
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]Nullen mit langsamen und schnellen Zeigern verschieben
Verschieben Sie alle Nullen ans Ende und bewahren Sie dabei die relative Reihenfolge der Elemente ungleich null. Der langsame Zeiger markiert die nächste Position für ein Element ungleich null. Der schnelle Zeiger sucht nach Werten ungleich null. Wenn der schnelle Zeiger einen solchen Wert findet, kopieren Sie ihn an die Position des langsamen Zeigers und bewegen Sie beide weiter. Füllen Sie nach dem Durchlauf die Positionen von slow bis zum Ende mit Nullen. O(n) Zeit, O(1) Speicher.
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]Array um einen Pivot-Wert partitionieren
Der Partitionsschritt von Quicksort ordnet die Elemente direkt im Array neu an, sodass alle Werte < pivot vor allen Werten >= pivot stehen. Das Lomuto-Schema verwendet einen langsamen Zeiger, der die letzte Position eines kleinen Elements markiert, und einen schnellen Zeiger, der vorwärts scannt. Wenn der schnelle Zeiger ein kleines Element findet, erhöhen Sie slow und tauschen die Elemente. Dies läuft in O(n) Zeit und benötigt O(1) zusätzlichen Speicher.
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 <= pivotMittleres Element einer verketteten Liste finden
Bei langsamen und schnellen Zeigern in einer verketteten Liste bewegt sich der schnelle Zeiger pro Schritt um zwei Knoten weiter, der langsame um einen. Wenn der schnelle Zeiger das Ende erreicht, befindet sich der langsame in der Mitte. Dieser Ansatz mit einem Durchlauf in O(n) ist deutlich übersichtlicher, als zunächst die Anzahl der Knoten zu zählen und anschließend bis zur Mitte zu laufen. Er wird als Teilschritt bei Merge-Sort für verkettete Listen und bei der Erkennung von Palindromen in verketteten Listen verwendet.
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)Zykluserkennung: Floyds Tortoise-and-Hare-Algorithmus
Bei Floyds Zykluserkennung werden der langsame und der schnelle Zeiger am Kopf einer verketteten Liste positioniert. Der langsame Zeiger bewegt sich um einen Knoten weiter, der schnelle um zwei. Wenn ein Zyklus existiert, wird der schnelle Zeiger den langsamen schließlich einholen, und beide treffen sich innerhalb des Zyklus. Wenn der schnelle Zeiger None erreicht, gibt es keinen Zyklus. Das Treffen ist garantiert, weil der schnelle Zeiger in jeder Iteration einen Schritt auf den langsamen gewinnt — bei einem Zyklus der Länge k treffen sie sich innerhalb von k Schritten, nachdem der langsame Zeiger in den Zyklus eingetreten ist.
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)) # TrueEinstiegspunkt eines Zyklus finden
Setzen Sie nach der Erkennung eines Zyklus (slow == fast) einen Zeiger zurück auf head. Bewegen Sie nun beide Zeiger jeweils um einen Schritt weiter. Sie treffen sich am Einstiegspunkt des Zyklus. Dies beruht auf der mathematischen Eigenschaft, dass die Entfernung vom Kopf bis zum Zykluseinstieg der Entfernung vom Treffpunkt bis zum Zykluseinstieg modulo der Zykluslänge entspricht. Dieses elegante mathematische Ergebnis tritt häufig in anspruchsvollen Interviewaufgaben auf.
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)Langsame und schnelle Zeiger bei glücklichen Zahlen
Langsame und schnelle Zeiger lassen sich über verkettete Listen hinaus auf jeden Prozess anwenden, der Zyklen bildet. Eine „glückliche Zahl“ durchläuft wiederholt die Quadratsummen ihrer Ziffern — wenn n nicht glücklich ist, gerät die Sequenz schließlich in eine Schleife. Erkennen Sie die Schleife mit dem langsamen Zeiger (ein Schritt = eine Quadratsumme der Ziffern) und dem schnellen Zeiger (zwei Schritte). Treffen sie sich bei 1, ist n glücklich; andernfalls steckt n in einem Zyklus, der nicht 1 enthält. Dies ist Floyds Algorithmus, angewendet auf eine virtuelle verkettete Liste von Werten.
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)N-tes Element vom Ende einer Liste
Finden Sie das n-te Element vom Ende einer verketteten Liste in einem einzigen Durchlauf mit zwei Zeigern. Bewegen Sie den schnellen Zeiger zunächst n Schritte voraus. Bewegen Sie anschließend beide Zeiger gemeinsam weiter, bis der schnelle das Ende erreicht — der langsame steht nun beim n-ten Element vom Ende. Um dieses Element zu löschen, behalten Sie einen Zeiger namens 'prev' eine Position hinter slow. Dies ist ein klassisches Problem zu verketteten Listen mit einem einzigen Durchlauf und vermeidet, zuerst die gesamte Länge zu zählen.
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->5Langsame und schnelle Zeiger bei String-Problemen
Das Denken in langsamen und schnellen Zeigern lässt sich auch auf Array- und String-Probleme anwenden. Beim Komprimieren eines lauflängenkodierten Strings markiert der langsame Zeiger die Schreibposition, während der schnelle Zeiger bis zum Ende jedes Laufs scannt. Wenn alle Zeichen des Laufs mit dem Zeichen des langsamen Zeigers übereinstimmen, bewegen Sie den schnellen Zeiger weiter; andernfalls speichern Sie den Lauf und aktualisieren den langsamen Zeiger. Dies erreicht O(n) in einem einzigen Durchlauf mit O(1) Speicher.
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']Zwischen langsamen und schnellen Zeigern sowie entgegengesetzten Enden wählen
Verwenden Sie Zeiger an entgegengesetzten Enden, wenn das Problem Paare mit einer bestimmten Summe, Palindromprüfungen oder ein von beiden Seiten zu verengendes Fenster umfasst. Verwenden Sie langsame und schnelle Zeiger, wenn Sie einen Schreibzeiger benötigen (zum Entfernen oder Verschieben von Elementen), wenn Sie die Struktur einer verketteten Liste verarbeiten (Mitte, Zyklus) oder wenn Sie Zyklen in einer beliebigen Wertesequenz erkennen. Beide Ansätze vermeiden verschachtelte Schleifen und erreichen O(n) — entscheidend ist die Struktur des Durchlaufs.
# 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)) # 5Kurzer Test
Testen Sie Ihr Verständnis der Konzepte aus Data Structures & Algorithms — Coding Interview Prep aus dieser Lektion.
Zusammenfassung der Lektion
In dieser Lektion haben Sie gelernt: Das Muster mit langsamen und schnellen Zeigern (Lese-Schreib-Muster) hält einen Schreibzeiger an der nächsten gültigen Position, während ein schneller Zeiger vorwärts scannt — die Grundlage für das Entfernen und Deduplizieren direkt im Array sowie das Verschieben von Nullen, Floyds Tortoise-and-Hare-Algorithmus erkennt Zyklen in O(n) Zeit und mit O(1) Speicher, indem er den Geschwindigkeitsunterschied zwischen zwei Zeigern ausnutzt, und nach der Erkennung eines Zyklus findet das Zurücksetzen eines Zeigers auf head und das gleich schnelle Weiterbewegen beider Zeiger den Zykluseinstieg aufgrund einer beweisbaren Gleichheit der Entfernungen. Als Nächstes untersuchen wir die Python-String-API für Interviews.
Lerne Python mit einem KI-Tutor — kostenlos
Schreibe und führe echten Code in deinem Browser aus, bekomme sofortige Hilfe von einem 24/7 KI-Tutor und setze dein Lernen im Web oder in der App fort.
- Kurse
- 30
- Lektionen
- 120
Häufig gestellte Fragen
Ist die Lektion „Zwei Zeiger: langsam und schnell“ kostenlos?
Ja — der vollständige Text von „Zwei Zeiger: langsam und schnell“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des DSA Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der DSA Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Zwei Zeiger: langsam und schnell“?
Wenden Sie das Muster mit langsamem und schnellem Zeiger an, um Duplikate In-Place zu entfernen, Nullen zu verschieben und Arrays um einen Pivot-Wert zu partitionieren. Du übst DSA Interview Prep mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um DSA Interview Prep zu starten?
Keine Vorkenntnisse erforderlich. DSA Interview Prep auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 4 von 4.
Wie lange dauert die Lektion „Zwei Zeiger: langsam und schnell“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser DSA Interview Prep-Lektion Code schreiben und ausführen?
Ja. Jede DSA Interview Prep-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- Array-Grundlagen und In-Place-Operationen
- Präfixsummen und laufende Summen
- Zwei Zeiger: entgegengesetzte Enden
- Zwei Zeiger: langsam und schnell