AtticTwo Pointers & Cycle Detection
Fast and slow pointer mechanics (Floyd's Tortoise and Hare), cycle detection, finding the middle, and list intersection
The Fast & Slow Pointer (Tortoise and Hare) pattern is the primary technique for solving single-pass linked list problems without extra memory. By advancing two pointers at different speeds (slow moves 1 step; fast moves 2 steps), you can detect cycles, locate the midpoint, or measure distance ratios in O(1) auxiliary space.
1. Finding the Middle Node
Advancing fast by two nodes for every one node slow traverses ensures that when fast reaches the end, slow is located precisely at the midpoint.
For [1, 2, 3, 4], returns node 3:
public ListNode middleNode(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow; // Points to middle (or second middle in even lists)
}2. Floyd's Cycle Detection (Linked List Cycle I)
Determine whether a linked list contains a cycle:
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) return false;
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
return true; // Pointers collided inside cycle!
}
}
return false; // Fast pointer hit null -> acyclic
}Why slow and fast Must Meet: Once both pointers enter a cycle of length C, the distance between fast and slow decreases by exactly 1 node on every single step (relative speed = 2 - 1 = 1). Because the gap shrinks by 1 node per iteration, fast cannot skip past slow; they must collide in <= C steps.
3. Locating the Cycle Entry Point (Linked List Cycle II)
To find the exact node where the cycle begins, use the mathematical relationship between the head, entry point, and collision point:
Head ----(Distance a)----> Entry ----(Distance b)----> CollisionPoint
^ |
|-----------(Distance c)--------|- Distance traveled by
slow:a + b - Distance traveled by
fast:a + b + k * C(whereC = b + c) - Since fast travels twice as fast:
2(a + b) = a + b + k * C, which simplifies toa = (k - 1)C + c
Conclusion: The distance from head to Entry (a) equals the distance from CollisionPoint to Entry (c)!
public ListNode detectCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
// Step 1: Detect collision
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
// Step 2: Reset one pointer to head and advance both at 1 step/tick
ListNode ptr1 = head;
ListNode ptr2 = slow;
while (ptr1 != ptr2) {
ptr1 = ptr1.next;
ptr2 = ptr2.next;
}
return ptr1; // Collision occurs exactly at the cycle entry!
}
}
return null; // No cycle
}4. Intersection of Two Linked Lists
Find the node at which the intersection of two singly linked lists begins:
By redirecting pointer A to headB upon reaching the end, and pointer B to headA, both pointers travel the exact same total distance (len_A + len_B):
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) return null;
ListNode pA = headA;
ListNode pB = headB;
// In the second pass, both pointers have traversed identical total lengths
while (pA != pB) {
pA = (pA == null) ? headB : pA.next;
pB = (pB == null) ? headA : pB.next;
}
return pA; // Either points to intersection node, or null if no overlap
}5. Remove N-th Node From End of List
Advance fast by n + 1 nodes first. Then advance both fast and slow together until fast reaches null; slow will be positioned directly before the target node:
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode fast = dummy;
ListNode slow = dummy;
// 1. Advance fast pointer so gap between fast and slow is n + 1
for (int i = 0; i <= n; i++) {
fast = fast.next;
}
// 2. Move both pointers at equal speed until fast hits end
while (fast != null) {
fast = fast.next;
slow = slow.next;
}
// 3. Delete target node
slow.next = slow.next.next;
return dummy.next;
}