Given the head of a linked list, return true if it contains a loop, using O(1) extra memory.

Keep slow and fast at the head. Each step, move slow one node and fast two nodes. If fast or fast.next is null, the list ends, so there is no loop. If slow and fast ever point at the same node, there is a loop, because inside a loop fast gains one node on slow every step and must catch it. Time is O(n) and memory is O(1).

Return the node where the loop begins, or null if there is no loop.

Detect the loop as above. When slow and fast meet, set slow back to the head and move both pointers one node at a time. They meet at the first node of the loop. The reason is that the distance from the head to the loop start is equal to the distance from the meeting point forward to the loop start (going round the loop), so equal-speed pointers arrive together. Time is O(n) and memory is O(1).

Return the middle node of a linked list in one pass. If there are two middle nodes, return the second.

Move slow one node and fast two nodes at a time while fast and fast.next exist. When the loop stops, fast has covered the whole list and slow has covered half of it, so slow is at the middle. With an even number of nodes this loop ends with slow on the second middle node. Time is O(n) with one pass and memory is O(1). Counting the length first would take two passes.

An array has n + 1 numbers, each from 1 to n, and exactly one number appears more than once. Find it without changing the array and with O(1) extra memory.

Treat the array as a linked list where index i points to the index nums[i]. Because there are n + 1 slots but only n possible values, and one value is repeated, two indexes point to the same index, which makes a loop. The entry to the loop is the duplicate number. Run Floyd's method: move slow one pointer and fast two pointers from index 0 until they meet, then restart slow at index 0 and move both one pointer at a time. They meet at the loop entry, which is the duplicate. Time is O(n), memory is O(1), and the array is not changed.

Fast and Slow Pointers

intermediate · 25 min · Asked often · Last reviewed 29 Oct 2026 · by TheLearningLoop Team

Key takeaways

Slow moves one step and fast moves two. When fast reaches the end, slow is at the middle.
If a list has a loop, fast laps slow inside it and they meet. If it has no loop, fast reaches the end. This is Floyd's cycle detection and it needs only O(1) memory.
After they meet, restart slow at the head and move both one step at a time. They meet again exactly where the loop starts.
Any "follow the pointer" problem can use this idea, including finding the duplicate in an array of n + 1 numbers from 1 to n.

New to this topic? Read the overview first: Data Structures & Algorithms: The Big Picture

When to use fast and slow pointers

Use fast and slow pointers when you have:

A linked list and want its middle in one pass, without knowing its length.
A question about whether a list or a chain of "next" links loops back on itself.
A need to find where a loop starts, for example the first repeated node.
A "follow the pointer" problem in disguise, such as find the duplicate number in an array of n + 1 numbers from 1 to n, or the happy number puzzle.
A strict limit of O(1) extra memory, which rules out remembering every node you have seen.

Use something else when:

You can afford O(n) memory and want the simplest code: a hash set of visited nodes finds a loop at once.
The data is an array that you can index: a normal two-pointer or a sliding window is easier.
You need the kth node from the end: use a fixed gap between two pointers, not different speeds.

There is no library to import. It is two references and a loop. Linked lists also exist in every standard library (see the real-world section), but loop detection is something you write yourself.

How fast and slow pointers work

Start two pointers at the head of the list. Slow moves one node per step. Fast moves two. They never move backwards.

If the list has a loop, fast gains one node on slow every step inside the loop, so they must meet. If it has no loop, fast reaches the end first.

Why they must meet: once both are inside the loop, the gap between them changes by exactly one node each step, so it cannot jump past zero without landing on it. There is no way for fast to hop over slow.

There are three uses, all with the same two pointers:

Find the middle. When fast reaches the end, slow has travelled half the distance, so it is at the middle. This takes one pass and no counting.
Detect a loop. If slow and fast ever stand on the same node, the list loops.
Find where the loop starts. After the pointers meet, put slow back at the head and move both one node at a time. They meet again exactly at the first node of the loop. The reason is that the distance from the head to the loop start equals the distance from the meeting point forward to the loop start, going round the loop.

The same idea works on an array. If nums[i] is "the next index to visit", the array is a linked list, and a repeated number makes two indexes point to the same place, which creates a loop.

Try it

Pick one of the three jobs, then press Run and step through. Slow is teal and fast is blue. A node holding both is orange, and green marks the answer.

Fast and slow pointers

Step 1 of 8 · Press Space to play, arrow keys to step

Examples:

slow, fast

Node → next node: 1 → 2, 2 → 3, 3 → 4, 4 → 5, 5 → 6, 6 → 3

Node 6 points back to node 3, so the list loops. Both pointers start at the first node.

moves:: 0
phase:: 1: look for a loop

Slow is teal and fast is blue. A node holding both is orange and green marks the answer. The moves counter counts each pointer move.

Speed

Things to try:

Find a loop, "Loop back to 3": the list 1 2 3 4 5 6 where the last node points back to node 3. The pointers meet on node 5 after 4 moves, then 2 more moves find that the loop starts at node 3. Choose "No loop" and fast reaches the end instead.
Find the middle, "Seven nodes": slow stops on node 4 after 3 moves, without counting the list first. With "Six nodes" there are two middle nodes and the loop returns the second, node 4.
Find the duplicate number: for 3 1 4 4 2 5 the pointers meet after 2 moves, then 2 more moves show the duplicate is 4. Try 1 3 4 2 2: the duplicate is 2.

Fast and slow pointer operations

Find the middle. Start both pointers at the head. While fast and the node after fast both exist, move slow one node and fast two. When the loop stops, slow is the middle (the second middle if the length is even).

Detect a loop. Use the same loop, and after each move check whether slow and fast are the same node. If they are, there is a loop. If the loop ends because fast ran out of nodes, there is none.

Find where the loop starts.

Run loop detection until slow and fast meet.
Move slow back to the head. Leave fast where it is.
Move both one node at a time until they meet. That node is the start of the loop.

Interview fact. Fast moves two steps, but the whole thing is still O(n) and uses O(1) memory: neither pointer visits a node more than a few times.

Fast and slow pointer time complexity

Job	Time	Extra memory
Find the middle	O(n), one pass	O(1)
Detect a loop	O(n)	O(1)
Find where the loop starts	O(n)	O(1)
Find the duplicate number in an array	O(n)	O(1), array not changed

If there is a loop, slow never walks more than about one full trip round the list before they meet, so the pointer work is bounded by a small multiple of n.

Fast and slow pointers vs other approaches

n is the number of nodes.

What you need	Fast and slow pointers	Hash set of visited nodes	Count the length first	Sort (arrays only)
Is there a loop	O(n) time, O(1) memory	O(n) time, O(n) memory	Cannot tell	Not applicable
Where does the loop start	O(n) time, O(1) memory	O(n) time, O(n) memory	Cannot tell	Not applicable
Middle of a list	One pass, O(1) memory	Not helpful	Two passes, O(1) memory	Not applicable
Duplicate in `n + 1` numbers	O(n) time, O(1) memory, array unchanged	O(n) time, O(n) memory	Not applicable	O(n log n) time, changes the array

The bold cells show where each wins. Fast and slow pointers win on memory. A hash set is simpler to write when memory is not a worry, and it never gets the "why does it work" question in an interview.

How to explain fast and slow pointers in an interview

Say what moves how fast: "slow moves one node, fast moves two".
Give the reason they meet: "inside a loop fast gains one node per step, so it cannot skip over slow".
For the loop start, say the second phase out loud: "I put slow back at the head and move both one step at a time".
State both costs: O(n) time and O(1) memory, and offer the hash set as the simpler O(n) memory version.
Mention the edge cases: an empty list, one node, a loop that starts at the head, and fast.next being null before you call fast.next.next.

Where you meet fast and slow pointers in real systems

You rarely write Floyd's method for its own sake, but the idea of "walk a chain and notice when it loops" appears all over software. Three examples are drawn out below, the first with code you can run, then more.

Example 1: Detecting a loop in a chain of records

A system stores records that each point to the next, such as a chain of redirects, a linked list of tasks, or "next job" links in a workflow. If an operator accidentally makes the last record point back to an earlier one, following the chain would never finish. A check with two pointers finds the loop and the record where it begins without storing every record it has seen. Open the example below to see the picture and the code.

Code: find where a loop starts in a linked listTime O(n)Memory O(1)

Records 1 and 2 lead into a loop made of records 3, 4, 5 and 6. Slow and fast meet inside the loop. Restarting slow at record 1 and moving both one step at a time makes them meet again at record 3, the loop start.

Run on six nodes where node 6 points back to node 3, all five versions report that the loop starts at node 3. After the loop is cut, all five report that there is no loop. The Rust version stores the list as indexes because Rust does not let a node point back at an earlier node without extra tools such as Rc. The C++ code builds with -std=c++17.

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None


def find_cycle_start(head):
    """Return the first node of the loop in a linked list, or None if there is no loop.

    Floyd's method: `slow` moves one node at a time and `fast` moves two. If the list
    loops, `fast` laps `slow` inside the loop and they meet. If it does not loop,
    `fast` reaches the end. After they meet, put `slow` back at the head and move both
    one node at a time: they meet again exactly where the loop starts.

    Time:   O(n). Each pointer visits each node a bounded number of times.
    Memory: O(1). Two references, however long the list is.
    """
    slow = fast = head
    while fast and fast.next:
        slow = slow.next               # one step
        fast = fast.next.next          # two steps
        if slow is fast:               # they met inside the loop
            slow = head
            while slow is not fast:    # same speed now, so they meet at the loop start
                slow = slow.next
                fast = fast.next
            return slow
    return None                        # fast reached the end: no loop

Example 2: Finding the middle of a list for merge sort

Merge sort on a linked list must split the list in half. Counting the nodes first and then walking to the middle reads the list twice. With fast and slow pointers, one pass finds the middle: when fast reaches the end, slow is there. The two halves are then sorted and merged.

Slow moves one node per step and fast moves two. After 3 steps fast is on the last node and slow is on node 4, the middle.

Example 3: Finding the duplicate in a list of ids

A batch job receives n + 1 ids, each between 1 and n, where one id was sent twice. Sorting would change the data, and a set would use extra memory. Reading each number as "the next position to visit" turns the array into a chain with a loop, and the start of the loop is the duplicate. For the array 3 1 4 4 2 5 the chain from position 0 goes 0, 3, 4, 2, 4, 2, ... and the loop starts at position 4, so the duplicate is 4.

Start at position 0, then follow each value to the position it names. The chain enters a loop between positions 4 and 2. The loop starts at position 4, which is the repeated number.

More real-world scenarios

4. Detecting circular dependencies

A build tool or package manager follows "depends on" links. If package A depends on B and B depends on A, following the chain never ends. Cycle detection finds the loop and reports it instead of hanging.

5. Garbage collection and reference cycles

Some memory managers count references to objects. Two objects that point at each other keep each other alive forever, a reference cycle. Detecting loops in the object graph is what lets such systems free them.

6. Corrupted file-system or database chains

Older file systems and some databases chain blocks or pages together with "next" links. A corrupted link can create a loop, and a repair tool walks each chain with two pointers so it can stop and report the bad block.

7. Linked-list based queues and caches

Caches and schedulers that keep items in a linked list sometimes need the middle item, for example to split work between two workers, and use one pass with fast and slow pointers instead of counting.

8. Random number generators

A pseudo-random generator produces each number from the previous one, so its sequence must eventually repeat. Floyd's method was used to measure the length of that cycle without storing the sequence.

9. Checking "happy numbers" and similar sequences

A number is happy if repeatedly replacing it with the sum of the squares of its digits reaches 1, and unhappy if the sequence loops. Running a fast and slow pointer along the sequence detects the loop with O(1) memory.

10. Network routing loops

If routers' "next hop" entries point in a circle, packets travel forever until they expire. Tools that trace a route follow the next-hop chain and use the same idea of spotting a repeat to flag a routing loop.

Language standard libraries

Standard libraries give you linked lists, but none of them expose loop detection, because their lists cannot contain a loop. You write the two-pointer loop yourself on your own node type.

Language	Structure or class	What it is under the hood	Notes
Java	`LinkedList`	Doubly linked list	Its nodes are private, so you define your own `Node` for loop-detection exercises.
C++	`std::list`, `std::forward_list`	Doubly and singly linked lists	Iterators cannot be made to loop, so write your own node struct for these problems.
C#	`LinkedList<T>`	Doubly linked list	Its nodes are `LinkedListNode<T>`. A user-defined node is used for loop problems.
Rust	`std::collections::LinkedList`	Doubly linked list	Safe Rust cannot easily build a loop, so examples store nodes in a `Vec` and use indexes.
Python	`collections.deque`	Blocks of items, not a classic linked list	Python has no built-in linked list. Define a small `Node` class.
Go	`container/list`	Doubly linked list	Elements are `*list.Element`. Define your own node for loop problems.
JavaScript	None built in	Objects with a `next` property	Write a `Node` class. `Array` and `Set` are used for the array-based problems.
Kotlin	`java.util.LinkedList`	The Java doubly linked list	Define your own node class for loop problems.

The pattern: the core is two references and a loop. The standard lists are for everyday use and cannot loop, so loop detection is something you write on a node type you control.

The takeaway

Whenever a system follows a chain of "next" links and must find the middle or notice a loop without storing every step, look for fast and slow pointers. When memory is not a concern, it usually uses a set of visited items instead because it is simpler to read.

Interview questions

Try answering out loud before you reveal hints. Interviewers care about how you reason, not just the final answer.

1.
Given the head of a linked list, return true if it contains a loop, using O(1) extra memory.
easy
2.
Return the node where the loop begins, or null if there is no loop.
medium
3.
Return the middle node of a linked list in one pass. If there are two middle nodes, return the second.
easy
4.
An array has n + 1 numbers, each from 1 to n, and exactly one number appears more than once. Find it without changing the array and with O(1) extra memory.
hard

Finished this lesson?

Progress is saved on this device. Create a free account to keep it everywhere.

← Previous

Two Pointers and Sliding Window

Prefix Sums and Difference Arrays

Topics:Fast and slow pointersFloyd cycle detectionTortoise and hareLinked listCycle detectionFind the duplicate number