Fast/Slow Pointers (Cycle & Midpoint)
A tortoise-and-hare pair of pointers moving at different speeds to detect a cycle or find a midpoint/kth-from-end node.
Core technique
Two pointers walk the same structure at different speeds. After moving, compare their node identities: inside a cycle, the fast pointer gains one node per step and eventually catches the slow pointer. In a finite list, fast reaches the end instead. The same two-speed loop finds the middle, returning the second middle when the length is even.
How to recognize it
- The input is a linked list and the question is about a cycle, the middle node, or the k-th node from the end.
- You must use O(1) extra space, which rules out a hash set of visited nodes.
- Repeated function calls or next-index links form a sequence over a finite set of states. Happy Number and Find the Duplicate Number use this structure; handle each problem's terminal state and constraints explicitly.
- You need to split a list into two halves, as in Reorder List or merge sort on a list.
Template
Cycle detection and finding the middle share one loop shape. Check fast before fast.next so you never dereference null. For the k-th node from the end, advance one pointer k steps first, then move both together.
Python
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
return True
return False
def middle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow # second middle when the length is evenJava
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;
}
return false;
}
ListNode middle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow; // second middle when the length is even
}JavaScript
function hasCycle(head) {
let slow = head;
let fast = head;
while (fast !== null && fast.next !== null) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) return true;
}
return false;
}
function middle(head) {
let slow = head;
let fast = head;
while (fast !== null && fast.next !== null) {
slow = slow.next;
fast = fast.next.next;
}
return slow; // second middle when the length is even
}Worked example: Linked List Cycle
- Take the list 3, 2, 0, -4 where the last node points back to the node holding 2. Both pointers start at 3.
- Step 1: slow moves to 2 and fast moves to 0.
- Step 2: slow moves to 0 and fast moves two nodes, from 0 through -4 to 2.
- Step 3: slow moves to -4 and fast moves from 2 through 0 to -4. Both pointers are on the same node, so a cycle exists.
- With no cycle, fast reaches null before the pointers can meet, the loop ends, and the answer is false.
- It cannot miss: once both pointers are inside the loop, fast closes the gap by exactly one node per step, so the gap reaches zero instead of jumping over it.
Complexity: O(n) time and O(1) extra space. The slow pointer enters the loop within n steps, and fast then catches it within one more lap of the loop.
Try Linked List Cycle on LeetCodeCommon mistakes
- Testing fast.next before fast. The condition must check fast first and fast.next second, or the last node throws a null error.
- Comparing node values instead of nodes. Lists can hold duplicate values, so compare the pointers themselves.
- Starting fast one node ahead without noticing that it moves the middle. On even lengths this decides whether you land on the first or second middle, which matters for Reorder List and Sort List.
- Stopping at the meeting point when the problem asks where the cycle starts, or for the duplicate value. After the pointers meet, reset one pointer to the head and move both one step at a time. They meet at the cycle entrance.
When this pattern does not fit
- You need to walk backwards or index freely. An array or a doubly linked list gives you that directly.
- Memory is not constrained and clarity matters more. A hash set of visited nodes is simpler, although interviewers often ask for the O(1) version as a follow-up.
- The input is a plain array with a target value rather than links. Two pointers or binary search fit better.