Schnelle & langsame Zeiger
Ein Zeiger, der doppelt so schnell läuft wie ein anderer, erkennt Zyklen, findet die Mitte und den n-ten vom Ende - in einem Durchlauf.
Deutsche Übersetzung in Arbeit
Diese Lektion ist noch nicht ins Deutsche übersetzt und wird daher auf Englisch angezeigt. Der Rest der Seite ist vollständig lokalisiert.
Auf dieser Seite
Some linked-list questions look like they need a second pass or extra memory - "find the middle," "does it have a cycle," "find the node k from the end." The fast and slow pointer technique (also called Floyd's tortoise and hare) answers all of them in a single pass with O(1) space, by running two pointers at different speeds.
Two speeds, one pass
Run one pointer (slow) one step at a time and another (fast) two steps at a time. Their relative
speed is what does the work. When fast reaches the end, slow is exactly halfway - so you've found
the middle without knowing the length:
// find the middle node in one pass — O(n) time, O(1) space
ListNode middle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next; // +1
fast = fast.next.next; // +2
}
return slow; // fast covered 2x, so slow is at the midpoint
}Cycle detection: the tortoise and hare
The most famous use: does a linked list have a cycle? If it does, the fast pointer will eventually
lap the slow one and they'll meet inside the loop - like a faster runner catching a slower one on a
circular track. If fast reaches null, there's no cycle.
// detect a cycle — O(n) time, O(1) space (no hash set needed)
boolean hasCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) return true; // they met → cycle
}
return false; // fast hit the end → no cycle
}Why must they meet if there's a cycle? Once both pointers are inside the loop, fast gains one step
on slow every iteration, so the gap between them shrinks by one each time - it can never jump over,
so it must eventually reach zero. This gives O(1) space, versus the obvious O(n)-space solution of
storing visited nodes in a hash set.
The nth from the end
The same idea with a fixed gap finds the k-th node from the end in one pass: advance fast k
steps first, then move both together until fast hits the end - now slow is k from the end.
Guard the fast pointer
fast moves two steps, so both fast and fast.next can be null. The loop condition must check
fast != null && fast.next != null (in that order, so short-circuiting prevents a
NullPointerException). Getting this guard wrong is the most common bug in fast/slow code.
Two runners start together; one runs twice as fast. On a straight track, the fast runner simply finishes first and leaves - no meeting. On a circular track, the fast runner keeps lapping and will inevitably come up behind the slow one and draw level. That's cycle detection: put two pointers on the list at different speeds - if the 'track' loops, they meet; if it ends, the fast one runs off the edge. And at the moment the fast runner has done a full lap, the slow one is exactly halfway - which is why the same trick finds the middle.
Determine whether a singly linked list reads the same forwards and backwards, using O(1) extra space. Combine two techniques you now know to do it in one pass plus a reversal.
Why do fast and slow pointers meet if (and only if) a linked list has a cycle?
Key takeaways
- Fast and slow pointers move at different speeds (typically 2x and 1x) to solve linked-list problems in one pass, O(1) space.
- When fast reaches the end, slow is at the middle - finding the midpoint without knowing the length.
- Floyd's cycle detection: if a cycle exists, fast laps slow and they meet; otherwise fast reaches null.
- A fixed k-step head start finds the k-th node from the end in one pass.
- Guard the loop with fast != null && fast.next != null (order matters) to avoid a NullPointerException.