Fast Slow Pointers 2026: Floyd's Cycle Detection [14+ Problems]

Last Updated: June 2026

Why Fast-Slow Pointers Matter

Candidates report fast-slow pointer questions in roughly 10-15% of FAANG linked list rounds. Based on public preparation resources and candidate-reported interview threads, Floyd's algorithm is the expected O(n) time O(1) space answer for any linked list cycle question. A hash set answer that uses O(n) space will often fail to impress interviewers at product companies.

The Core Algorithm

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def has_cycle(head):
    """
    Slow: 1 step. Fast: 2 steps.
    If cycle: fast laps slow, they meet inside cycle.
    If no cycle: fast reaches None.
    Time: O(n)  Space: O(1)
    """
    slow = fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True

    return False

Why Floyd's Algorithm Works

No cycle:
  Fast runs off the end: None. Detect immediately.

With cycle of length c, list length n:
  After k steps: slow at position k, fast at position 2k.
  They meet when 2k - k = 0 mod c, i.e., k = multiple of c.
  So they meet after at most c steps inside the cycle.

Finding cycle start:
  If they meet at position m inside cycle,
  distance from head to cycle start = distance from meeting point to cycle start.
  Reset one pointer to head, move both 1 step at a time.
  They meet exactly at cycle start.

Practice Questions with Solutions

Problem 1: Linked List Cycle (EASY)

Asked at: Amazon, Microsoft, Google, TCS

def has_cycle_v2(head):
    slow = fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True

    return False

Complexity: Time O(n), Space O(1)

Problem 2: Find Cycle Start (MEDIUM)

Asked at: Amazon, Google, Microsoft - the follow-up to cycle detection

def detect_cycle(head):
    """
    Step 1: Detect meeting point.
    Step 2: Reset one pointer to head. Move both 1 step.
    They meet at cycle entry.
    Time: O(n)  Space: O(1)
    """
    slow = fast = head

    # Step 1: Find meeting point
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            break
    else:
        return None  # no cycle

    # Step 2: Find cycle start
    slow = head
    while slow != fast:
        slow = slow.next
        fast = fast.next

    return slow  # cycle start node

Complexity: Time O(n), Space O(1)

Problem 3: Middle of Linked List (EASY)

Asked at: Amazon, Microsoft, TCS, Infosys

def middle_node(head):
    """
    Slow moves 1 step, fast moves 2 steps.
    When fast reaches end, slow is at middle.
    For even-length list, returns second middle.
    Time: O(n)  Space: O(1)
    """
    slow = fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    return slow

# Example: 1->2->3->4->5 -> returns node 3
# Example: 1->2->3->4 -> returns node 3 (second middle)

Complexity: Time O(n), Space O(1)

Problem 4: Happy Number (EASY)

Asked at: Google, Amazon, Microsoft

def is_happy(n):
    """
    Happy number: repeatedly sum of squares of digits eventually reaches 1.
    Unhappy: enters a cycle not including 1.
    Apply Floyd's to detect cycle.
    Time: O(log n)  Space: O(1)
    """
    def sum_of_squares(num):
        total = 0
        while num:
            digit = num % 10
            total += digit * digit
            num //= 10
        return total

    slow = n
    fast = sum_of_squares(n)

    while fast != 1 and slow != fast:
        slow = sum_of_squares(slow)
        fast = sum_of_squares(sum_of_squares(fast))

    return fast == 1

# Example
print(is_happy(19))  # True: 1^2+9^2=82, 8^2+2^2=68, ... -> 1
print(is_happy(2))   # False: enters cycle

Complexity: Time O(log n), Space O(1)

Problem 5: Find the Duplicate Number (MEDIUM)

Asked at: Amazon, Google, Facebook - classic Floyd's on array

def find_duplicate(nums):
    """
    Treat nums as implicit linked list: i -> nums[i].
    Since nums has n+1 elements in [1..n], one duplicate = one cycle.
    Apply Floyd's to find cycle start = duplicate number.
    Time: O(n)  Space: O(1)
    """
    slow = fast = nums[0]

    # Step 1: Find meeting point
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast:
            break

    # Step 2: Find cycle start
    slow = nums[0]
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]

    return slow

# Example
print(find_duplicate([1, 3, 4, 2, 2]))  # 2
print(find_duplicate([3, 1, 3, 4, 2]))  # 3

Complexity: Time O(n), Space O(1)

Problem 6: Palindrome Linked List (MEDIUM)

Asked at: Amazon, Facebook, Microsoft

def is_palindrome(head):
    """
    1. Find middle with fast-slow.
    2. Reverse second half.
    3. Compare both halves.
    4. Restore list (optional but good practice).
    Time: O(n)  Space: O(1)
    """
    # Find middle
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    # Reverse second half
    prev = None
    curr = slow
    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node

    # Compare
    left, right = head, prev
    result = True
    while right:
        if left.val != right.val:
            result = False
            break
        left = left.next
        right = right.next

    return result

Complexity: Time O(n), Space O(1)

Problem 7: Remove Nth Node From End (MEDIUM)

Asked at: Amazon, Microsoft, Facebook

def remove_nth_from_end(head, n):
    """
    Two pointers with fixed gap of n.
    When fast.next is None, slow.next is node to remove.
    Time: O(n)  Space: O(1)
    """
    dummy = ListNode(0)
    dummy.next = head
    fast = slow = dummy

    # Advance fast n+1 steps
    for _ in range(n + 1):
        fast = fast.next

    # Move together until fast is None
    while fast:
        slow = slow.next
        fast = fast.next

    slow.next = slow.next.next
    return dummy.next

Complexity: Time O(n), Space O(1)

Problem 8: Reorder List (MEDIUM)

Asked at: Amazon, Microsoft, Facebook - combines fast-slow + reverse + merge

def reorder_list(head):
    """
    Given 1->2->3->4->5, produce 1->5->2->4->3.
    Step 1: Find middle with fast-slow.
    Step 2: Reverse second half.
    Step 3: Merge alternately.
    Time: O(n)  Space: O(1)
    """
    # Find middle
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    # Reverse second half
    second = slow.next
    slow.next = None
    prev = None
    while second:
        next_node = second.next
        second.next = prev
        prev = second
        second = next_node
    second = prev

    # Merge two halves
    first = head
    while second:
        tmp1, tmp2 = first.next, second.next
        first.next = second
        second.next = tmp1
        first = tmp1
        second = tmp2

Complexity: Time O(n), Space O(1)

Problem 9: Linked List Cycle Length (EASY)

Asked at: Service company assessments

def cycle_length(head):
    """
    After detecting meeting point, count steps to return to meeting point.
    Time: O(n)  Space: O(1)
    """
    slow = fast = head

    # Find meeting point
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            break
    else:
        return 0  # no cycle

    # Count cycle length
    length = 1
    fast = fast.next
    while fast != slow:
        fast = fast.next
        length += 1

    return length

Complexity: Time O(n), Space O(1)

Problem 10: Sort List (MEDIUM)

Asked at: Amazon, Microsoft - uses fast-slow to split

def sort_list(head):
    """
    Merge sort on linked list.
    Find middle with fast-slow to split.
    Merge sorted halves.
    Time: O(n log n)  Space: O(log n) call stack
    """
    if not head or not head.next:
        return head

    # Find middle
    slow, fast = head, head.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    mid = slow.next
    slow.next = None

    # Sort both halves
    left = sort_list(head)
    right = sort_list(mid)

    # Merge
    dummy = ListNode(0)
    curr = dummy
    while left and right:
        if left.val <= right.val:
            curr.next = left
            left = left.next
        else:
            curr.next = right
            right = right.next
        curr = curr.next

    curr.next = left or right
    return dummy.next

Complexity: Time O(n log n), Space O(log n)

Problem 11: Intersection of Two Linked Lists (EASY)

Asked at: Amazon, Microsoft, Facebook

Problem: Find the node where two singly linked lists merge, or None if they do not.

def get_intersection_node(headA, headB):
    """
    Two pointers that switch lists at the end. After at most one
    switch, both have traveled lenA + lenB, so they align at the
    intersection (or both hit None together).
    Time: O(m + n)  Space: O(1)
    """
    a, b = headA, headB
    while a is not b:
        a = a.next if a else headB
        b = b.next if b else headA
    return a            # intersection node or None

# If lenA = 5, lenB = 6, after the swap both pointers have walked
# 11 nodes and meet exactly at the shared tail.

Why it works: pointer a walks list A then list B; pointer b walks list B then list A. Both cover the same total distance, so they arrive at the first shared node simultaneously. If there is no intersection, both reach None after that distance and the loop ends.

Complexity: Time O(m + n), Space O(1)

Problem 12: Circular Array Loop (MEDIUM)

Asked at: Google, Amazon

Problem: Each element is a jump (positive forward, negative backward, wrap-around). Return True if a cycle exists that is all-forward or all-backward and longer than one element.

def circular_array_loop(nums):
    """
    Floyd's on each start index. Track direction; a valid cycle must
    keep one consistent direction and have length > 1.
    Time: O(n)  Space: O(1)
    """
    n = len(nums)

    def next_index(i):
        return (i + nums[i]) % n

    for start in range(n):
        if nums[start] == 0:
            continue
        slow = fast = start
        while True:
            # direction must stay consistent
            if nums[slow] * nums[next_index(slow)] <= 0:
                break
            if nums[fast] * nums[next_index(fast)] <= 0:
                break
            if nums[next_index(fast)] * nums[next_index(next_index(fast))] <= 0:
                break
            slow = next_index(slow)
            fast = next_index(next_index(fast))
            if slow == fast:
                if slow == next_index(slow):   # length-1 loop is invalid
                    break
                return True
    return False

# Example
print(circular_array_loop([2, -1, 1, 2, 2]))   # True
print(circular_array_loop([-1, 2]))             # False

Complexity: Time O(n), Space O(1)

Problem 13: Remove Duplicates from Sorted List II (MEDIUM)

Asked at: Amazon, Microsoft

Problem: Remove all nodes that have duplicate values, leaving only distinct values.

def delete_duplicates(head):
    """
    Dummy head plus a slow pointer marking the last confirmed-unique
    node, while a fast scan skips over entire duplicate runs.
    Time: O(n)  Space: O(1)
    """
    dummy = ListNode(0, head)
    prev = dummy
    curr = head
    while curr:
        if curr.next and curr.val == curr.next.val:
            while curr.next and curr.val == curr.next.val:
                curr = curr.next          # skip the whole duplicate run
            prev.next = curr.next         # unlink all duplicates
        else:
            prev = prev.next
        curr = curr.next
    return dummy.next

# Example: 1->2->3->3->4->4->5  becomes  1->2->5

This is the slow-fast pointer idea applied to deletion: prev lags behind as the confirmed-unique boundary while curr races ahead to find where the next distinct value begins.

Complexity: Time O(n), Space O(1)

The Math Behind Floyd's Cycle Start

The cycle-start step looks like magic, so be ready to prove it. Let the distance from the head to the cycle entry be F nodes, and let the meeting point sit C nodes into the cycle, where the cycle has length L.

When slow and fast meet, slow has traveled F + C and fast has traveled F + C + kL for some number of full loops k, because fast is exactly the distance of whole cycles ahead. Since fast moves twice as fast, its distance is double slow's:

2 (F + C) = F + C + k L
=>  F + C = k L
=>  F = k L - C

So F equals a whole number of cycle lengths minus C. This means if you place one pointer at the head and leave the other at the meeting point, and advance both one step at a time, the head pointer walks F steps to reach the entry, while the meeting-point pointer walks F steps which is k L minus C, landing it exactly at the entry too. They meet precisely at the cycle start. That algebra is the entire justification, and stating it cleanly is a strong senior signal.

How to Recognize a Fast-Slow Pointer Problem

The pattern announces itself through a small set of cues. The clearest is a linked list combined with a requirement for O(1) extra space: you cannot afford a hash set of visited nodes, so two pointers moving at different speeds become the tool.

Any mention of a cycle, a loop, or "does this list repeat" is a direct flag for Floyd's tortoise and hare. The same applies to disguised lists: the Happy Number treats digit-square sums as next pointers, and Find the Duplicate treats array values as next indices, so a sequence that eventually repeats is a cycle in disguise.

A second family is positional queries on a list in a single pass: the middle node, the kth node from the end, or splitting a list in half. Here the two pointers move at the same speed but start a fixed gap apart, or one moves twice as fast so that when it reaches the end the slow one sits at the midpoint.

A third family combines the midpoint split with reversal or merging: palindrome check, reorder list, and sort list all find the middle with fast-slow, then operate on the halves. If a linked-list problem asks you to compare or interleave the front and back, finding the middle in one pass is almost always the first step.

If the data is an array with no ordering and no implicit successor function, this pattern usually does not apply; reach instead for the standard two-pointer or sliding-window techniques.

Fast-Slow Pointer Problems Map

Common Mistakes

1. Initializing fast = head.next instead of head: For cycle detection, start both at head. Starting fast one step ahead changes the phase relationship.
2. Forgetting to handle no-cycle case: Always check while fast and fast.next or use a break with an else clause.
3. Not using a dummy node for removal: remove_nth_from_end needs a dummy head to handle the case where the head itself is removed.
4. Modifying list without restoring: is_palindrome reverses the second half. Restore it if the problem requires the list structure to remain intact.

Related Articles

• Two Pointers Pattern Questions 2026
• Recursion and Backtracking Patterns 2026
• Must-Do Coding Questions
• Arrays Questions Placement
• Stack Queue Questions Placement