Autocoder

Fast and slow pointers interview questions with solutions

Last updated 2026-11-19

The fast and slow pointer technique, also called Floyd's tortoise and hare, moves two pointers through a sequence at different speeds, typically one step and two steps at a time. If the sequence has a cycle, the fast pointer eventually laps the slow one and they meet. If it does not, the fast pointer reaches the end first. Because the fast pointer covers twice the distance, when it hits the end the slow pointer is exactly in the middle.

This gives O(1)-space answers to questions that otherwise need a hash set: does a list have a cycle, where does the cycle start, where is the middle, does a number sequence repeat. The ten problems below also include an array treated as an implicit linked list. For general list manipulation see linked list questions; for the two-index pattern on arrays see two pointers questions.

Problems10, easy to hard
LanguagesPython and Java
Core ideaTwo speeds; meeting proves a cycle

Why the pointers must meet

Inside a cycle of length L, each step the fast pointer closes the gap to the slow pointer by one. So after at most L steps in the cycle they coincide. They cannot jump over each other, because the gap changes by exactly one each step.

To find where the cycle starts, let the cycle start be at distance a from the head, and the meeting point be b steps into the cycle. Then 2(a + b) = a + b + kL, so a = kL - b: a pointer starting at the head and another starting at the meeting point, both moving one step at a time, meet exactly at the cycle start.

List node used below

The list problems use a singly linked node with a value and a next pointer.

python
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
java
class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

Fast and slow pointers interview questions with solutions: questions with worked answers

  1. 1

    Detect whether a linked list has a cycle.

    easy

    Move slow by one and fast by two. If fast or its next becomes null, the list ends and there is no cycle. If slow and fast ever point to the same node, there is a cycle. A hash set also works but uses O(n) space. Time O(n), space O(1).. Edge cases: empty list, a single node pointing to itself, a list of two nodes with a cycle.

    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
    java
    import java.util.*;
    
    class Solution {
        static 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;
        }
    }
  2. 2

    Find the middle node of a linked list (the second middle for even length).

    easy

    Advance slow by one and fast by two while fast and fast.next exist. When fast runs off the end, slow sits at the middle. For an even number of nodes the loop condition makes slow stop on the second of the two middle nodes. Change the condition to fast.next and fast.next.next to get the first middle. Time O(n), space O(1).. Edge cases: single node, two nodes, empty list.

    python
    def middle_node(head):
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow
    java
    import java.util.*;
    
    class Solution {
        static ListNode middleNode(ListNode head) {
            ListNode slow = head, fast = head;
            while (fast != null && fast.next != null) {
                slow = slow.next;
                fast = fast.next.next;
            }
            return slow;
        }
    }
  3. 3

    Find the length of the cycle in a linked list.

    medium

    First find a meeting point with slow and fast. Then keep one pointer fixed and move the other one step at a time, counting steps until it returns to the meeting point. That count is the cycle length. Return 0 if there is no cycle. Time O(n), space O(1).. Edge cases: no cycle (0), a self-loop (length 1), the whole list is the cycle.

    python
    def cycle_length(head):
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow is fast:
                count, cur = 1, slow.next
                while cur is not slow:
                    cur = cur.next
                    count += 1
                return count
        return 0
    java
    import java.util.*;
    
    class Solution {
        static int cycleLength(ListNode head) {
            ListNode slow = head, fast = head;
            while (fast != null && fast.next != null) {
                slow = slow.next;
                fast = fast.next.next;
                if (slow == fast) {
                    int count = 1;
                    for (ListNode cur = slow.next; cur != slow; cur = cur.next) count++;
                    return count;
                }
            }
            return 0;
        }
    }
  4. 4

    Find the node where a cycle begins.

    medium

    After slow and fast meet, move one pointer back to the head. Advance both one step at a time; they meet at the node where the cycle begins. The distance from the head to the cycle start equals the distance from the meeting point forward to the cycle start, modulo the cycle length. Return null if no cycle exists. Time O(n), space O(1).. Edge cases: no cycle (null), cycle starting at the head, a self-loop at the last node.

    python
    def detect_cycle(head):
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow is fast:
                slow = head
                while slow is not fast:
                    slow = slow.next
                    fast = fast.next
                return slow
        return None
    java
    import java.util.*;
    
    class Solution {
        static ListNode detectCycle(ListNode head) {
            ListNode slow = head, fast = head;
            while (fast != null && fast.next != null) {
                slow = slow.next;
                fast = fast.next.next;
                if (slow == fast) {
                    slow = head;
                    while (slow != fast) {
                        slow = slow.next;
                        fast = fast.next;
                    }
                    return slow;
                }
            }
            return null;
        }
    }
  5. 5

    Happy number using fast and slow pointers instead of a set.

    easy

    Define next(n) as the sum of squares of the digits of n. The sequence either reaches 1 (which maps to itself) or cycles. Treat it like a linked list: slow takes one step of next, fast takes two. If fast reaches 1, the number is happy; if slow and fast meet at any other value, it cycles forever. This uses O(1) space. Time O(log n) per step with a bounded number of steps, space O(1).. Edge cases: n = 1 (happy), a number in the unhappy cycle such as 4, n = 7 (happy).

    python
    def is_happy(n):
        def nxt(x):
            return sum(int(d) ** 2 for d in str(x))
        slow, fast = n, nxt(n)
        while fast != 1 and slow != fast:
            slow = nxt(slow)
            fast = nxt(nxt(fast))
        return fast == 1
    java
    import java.util.*;
    
    class Solution {
        static boolean isHappy(int n) {
            int slow = n, fast = next(n);
            while (fast != 1 && slow != fast) {
                slow = next(slow);
                fast = next(next(fast));
            }
            return fast == 1;
        }
        static int next(int x) {
            int s = 0;
            while (x > 0) {
                int d = x % 10;
                s += d * d;
                x /= 10;
            }
            return s;
        }
    }
  6. 6

    Find the duplicate number in an array of n + 1 integers in 1..n without modifying it and using O(1) space.

    medium

    Treat the array as a linked list where index i points to a[i]. Because there are n + 1 values in 1..n, two indices point to the same node, which creates a cycle whose entrance is the duplicate value. Find the meeting point with slow and fast, reset one pointer to index 0, then move both one step at a time; they meet at the duplicate. Time O(n), space O(1).. Edge cases: duplicate repeated many times, the duplicate is 1 or n, array of length 2 ([1, 1]).

    python
    def find_duplicate(a):
        slow = fast = 0
        while True:
            slow = a[slow]
            fast = a[a[fast]]
            if slow == fast:
                break
        slow = 0
        while slow != fast:
            slow = a[slow]
            fast = a[fast]
        return slow
    java
    import java.util.*;
    
    class Solution {
        static int findDuplicate(int[] a) {
            int slow = 0, fast = 0;
            do {
                slow = a[slow];
                fast = a[a[fast]];
            } while (slow != fast);
            slow = 0;
            while (slow != fast) {
                slow = a[slow];
                fast = a[fast];
            }
            return slow;
        }
    }
  7. 7

    Palindrome linked list in O(1) extra space.

    medium

    Find the middle with slow and fast pointers, reverse the second half in place, then compare the first half with the reversed second half node by node. Any mismatch means it is not a palindrome. Reverse the second half again if the caller expects the list unchanged. Time O(n), space O(1).. Edge cases: empty or single node (true), odd and even lengths, lists whose halves differ only at the middle.

    python
    def is_palindrome(head):
        slow = fast = head
        while fast and fast.next:
            slow, fast = slow.next, fast.next.next
        prev = None
        while slow:
            slow.next, prev, slow = prev, slow, slow.next
        a, b = head, prev
        while b:
            if a.val != b.val:
                return False
            a, b = a.next, b.next
        return True
    java
    import java.util.*;
    
    class Solution {
        static boolean isPalindrome(ListNode head) {
            ListNode slow = head, fast = head;
            while (fast != null && fast.next != null) {
                slow = slow.next;
                fast = fast.next.next;
            }
            ListNode prev = null;
            while (slow != null) {
                ListNode nxt = slow.next;
                slow.next = prev;
                prev = slow;
                slow = nxt;
            }
            ListNode a = head, b = prev;
            while (b != null) {
                if (a.val != b.val) return false;
                a = a.next;
                b = b.next;
            }
            return true;
        }
    }
  8. 8

    Intersection of two singly linked lists: find the node where they merge.

    medium

    Walk one pointer along list A and then list B, and the other along B and then A. Both pointers travel lenA + lenB steps in total, so they line up at the intersection, or both become null together if the lists do not meet. It is the same equal-distance idea as fast and slow pointers. Time O(n + m), space O(1).. Edge cases: no intersection (null), one list empty, intersection at the head.

    python
    def get_intersection_node(a, b):
        p, q = a, b
        while p is not q:
            p = p.next if p else b
            q = q.next if q else a
        return p
    java
    import java.util.*;
    
    class Solution {
        static ListNode getIntersectionNode(ListNode a, ListNode b) {
            ListNode p = a, q = b;
            while (p != q) {
                p = p == null ? b : p.next;
                q = q == null ? a : q.next;
            }
            return p;
        }
    }
  9. 9

    Delete the middle node of a linked list.

    medium

    Use a dummy node before the head so a one-node list works. Start slow at the dummy and fast at the head. Advance slow by one and fast by two while fast and fast.next exist. At the end slow is the node just before the middle, so set slow.next = slow.next.next. The middle index is floor(n / 2). Time O(n), space O(1).. Edge cases: one node (returns empty), two nodes (second removed), odd and even lengths.

    python
    def delete_middle(head):
        dummy = ListNode(0, head)
        slow, fast = dummy, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        slow.next = slow.next.next
        return dummy.next
    java
    import java.util.*;
    
    class Solution {
        static ListNode deleteMiddle(ListNode head) {
            ListNode dummy = new ListNode(0);
            dummy.next = head;
            ListNode slow = dummy, fast = head;
            while (fast != null && fast.next != null) {
                slow = slow.next;
                fast = fast.next.next;
            }
            slow.next = slow.next.next;
            return dummy.next;
        }
    }
  10. 10

    Circular array loop: does a cycle of length greater than one exist where all moves go in the same direction?

    hard

    Treat each index as a node with an edge to (i + nums[i]) mod n. For each start, run slow and fast pointers, stopping a path if the direction changes or a step lands on a visited (zeroed) cell. A meeting point is a valid cycle unless it is a self-loop (the step returns to the same index). After a failed start, zero out the cells on that path so they are never revisited, which keeps the total work linear. Time O(n), space O(1) (the array is modified).. Edge cases: a self-loop such as [1] with n = 1 (invalid), mixed directions (invalid), a cycle of length two or more.

    python
    def circular_array_loop(nums):
        n = len(nums)
        def nxt(i):
            return (i + nums[i]) % n
        for i in range(n):
            if nums[i] == 0:
                continue
            forward = nums[i] > 0
            slow = fast = i
            while True:
                s = nxt(slow)
                if nums[s] == 0 or (nums[s] > 0) != forward:
                    break
                f1 = nxt(fast)
                if nums[f1] == 0 or (nums[f1] > 0) != forward:
                    break
                f2 = nxt(f1)
                if nums[f2] == 0 or (nums[f2] > 0) != forward:
                    break
                slow, fast = s, f2
                if slow == fast:
                    if slow != nxt(slow):
                        return True
                    break
            j = i
            while nums[j] != 0 and (nums[j] > 0) == forward:
                k = nxt(j)
                nums[j] = 0
                j = k
        return False
    java
    import java.util.*;
    
    class Solution {
        static boolean circularArrayLoop(int[] nums) {
            int n = nums.length;
            for (int i = 0; i < n; i++) {
                if (nums[i] == 0) continue;
                boolean forward = nums[i] > 0;
                int slow = i, fast = i;
                while (true) {
                    int s = next(nums, slow, n);
                    if (nums[s] == 0 || (nums[s] > 0) != forward) break;
                    int f1 = next(nums, fast, n);
                    if (nums[f1] == 0 || (nums[f1] > 0) != forward) break;
                    int f2 = next(nums, f1, n);
                    if (nums[f2] == 0 || (nums[f2] > 0) != forward) break;
                    slow = s;
                    fast = f2;
                    if (slow == fast) {
                        if (slow != next(nums, slow, n)) return true;
                        break;
                    }
                }
                int j = i;
                while (nums[j] != 0 && (nums[j] > 0) == forward) {
                    int k = next(nums, j, n);
                    nums[j] = 0;
                    j = k;
                }
            }
            return false;
        }
        static int next(int[] nums, int i, int n) {
            return ((i + nums[i]) % n + n) % n;
        }
    }

Frequently asked questions

Why does the fast pointer move exactly two steps?

Two steps means the gap to the slow pointer shrinks by one each iteration inside a cycle, so they cannot skip past each other. A speed of three or more can in some cycle lengths, though it still detects the cycle eventually.

Can I detect a cycle with a hash set instead?

Yes, by storing visited nodes. It is simpler but uses O(n) memory, while fast and slow pointers use O(1). Interviewers often ask for the O(1) version as a follow-up.

How do I find where the cycle starts?

After the pointers meet, restart one at the head and move both one step at a time. They meet at the cycle start, a result that follows from the distances in the cycle.

What other problems use this idea?

Finding the middle, the kth node from the end with a gap, palindromic lists and duplicate detection in arrays treated as linked lists. See linked list questions for list tools.

Does the technique work on arrays?

Yes, when the array defines a function from index to next index, as in the find-the-duplicate and circular loop problems. See also cyclic sort questions.

Related guides

More in DSA Interview Questions

See all in this section