LeetCode Patterns ·

🎯 Fast & Slow Pointer

1️⃣ Core Framework

When discussing Fast & Slow Pointer, I frame it as:

What problem pattern it solves
Why speed difference creates useful information
Linked list cycle detection
Finding the middle of a linked list
Finding cycle entry point
Happy number
Detecting duplicates using cycle logic
Common edge cases
Complexity analysis
Senior-level explanation

2️⃣ What Problem Are We Solving?

Fast and slow pointer is a technique where two pointers move at different speeds.

Usually:

slow pointer moves 1 step
fast pointer moves 2 steps

It is commonly used for:

Detecting cycles
Finding the middle of a linked list
Finding the entry point of a cycle
Checking whether a number sequence loops
Detecting duplicates in constrained arrays
Solving problems where repeated states imply a cycle

The core idea is:

If there is a cycle,
a faster pointer will eventually catch a slower pointer.

👉 Interview Answer

Fast and slow pointer is a two-pointer technique where one pointer moves faster than the other.

It is especially useful for linked lists and cycle detection problems.

If a cycle exists, the fast pointer will eventually meet the slow pointer.

If no cycle exists, the fast pointer reaches the end.

3️⃣ Why Fast & Slow Pointer Works

Basic Intuition

Imagine two runners on a circular track.

slow runner: 1 step each time
fast runner: 2 steps each time

If the track is circular:

fast runner eventually catches slow runner

If the path is not circular:

fast runner reaches the end

Linked List View

In a linked list:

Acyclic list:
1 → 2 → 3 → 4 → null

Cyclic list:
1 → 2 → 3 → 4
        ↑     ↓
        6 ← 5

Fast pointer either:

reaches null

or:

meets slow pointer inside the cycle

👉 Interview Answer

The reason fast and slow pointers work is the relative speed difference.

Inside a cycle, fast gains one node on slow at each step.

Since the cycle has finite length, fast must eventually catch slow.

If there is no cycle, fast simply reaches null.

4️⃣ Floyd’s Cycle Detection

Also Called

Tortoise and Hare Algorithm

The slow pointer is the tortoise.

The fast pointer is the hare.

Core Algorithm

slow = head
fast = head

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

    if slow == fast:
        return True

return False

Key Idea

If fast catches slow → cycle exists
If fast reaches null → no cycle

👉 Interview Answer

Floyd’s cycle detection algorithm uses two pointers moving at different speeds.

Slow moves one step at a time.

Fast moves two steps at a time.

If they meet, there is a cycle.

If fast reaches null, there is no cycle.

5️⃣ Linked List Cycle

Problem

Given the head of a linked list, determine whether the linked list has a cycle.

Code

def has_cycle(head):
    slow = head
    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)

Why O(n)?

Even though fast moves faster, it does not visit nodes indefinitely before detection.

If there is no cycle:

fast reaches the end

If there is a cycle:

fast meets slow within the cycle

👉 Interview Answer

To detect a linked list cycle, I use fast and slow pointers.

Slow moves one node each time.

Fast moves two nodes each time.

If the list has a cycle, fast eventually meets slow.

If fast reaches null, the list has no cycle.

6️⃣ Finding the Middle of a Linked List

Problem

Given a linked list, return the middle node.

1 → 2 → 3 → 4 → 5
middle = 3

1 → 2 → 3 → 4 → 5 → 6
middle = 4

Code

def middle_node(head):
    slow = head
    fast = head

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

    return slow

Why It Works

When fast moves twice as fast:

fast travels 2x distance
slow travels 1x distance

So when fast reaches the end:

slow is at the middle

👉 Interview Answer

To find the middle of a linked list, I use slow and fast pointers.

Fast moves two steps while slow moves one step.

When fast reaches the end, slow is at the middle node.

7️⃣ First Middle vs Second Middle

Even Length List

For even-length linked lists:

1 → 2 → 3 → 4

There are two middle candidates:

2 and 3

The common template returns the second middle:

Return Second Middle

def second_middle(head):
    slow = head
    fast = head

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

    return slow

Return First Middle

def first_middle(head):
    slow = head
    fast = head

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

    return slow

👉 Interview Answer

For even-length linked lists, I clarify whether the problem wants the first middle or the second middle.

The common slow-fast template returns the second middle.

If I need the first middle, I adjust the loop condition so slow stops one node earlier.

8️⃣ Linked List Cycle II

Problem

Given a linked list with a cycle, return the node where the cycle begins.

Algorithm

Step 1: Detect meeting point.

slow and fast meet inside the cycle

Step 2: Move one pointer to head.

ptr1 = head
ptr2 = meeting point

Step 3: Move both one step at a time.

They meet at cycle entry.

Code

def detect_cycle(head):
    slow = head
    fast = head

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

        if slow == fast:
            break
    else:
        return None

    ptr1 = head
    ptr2 = slow

    while ptr1 != ptr2:
        ptr1 = ptr1.next
        ptr2 = ptr2.next

    return ptr1

👉 Interview Answer

First, I use fast and slow pointers to detect whether a cycle exists.

If they meet, I reset one pointer to the head and keep the other at the meeting point.

Then I move both one step at a time.

The node where they meet again is the cycle entry point.

9️⃣ Why Cycle Entry Logic Works

Define Distances

Let:

a = distance from head to cycle entry
b = distance from cycle entry to meeting point
c = remaining distance from meeting point back to cycle entry

Cycle length:

b + c

When Slow and Fast Meet

Slow travels:

a + b

Fast travels:

2(a + b)

Fast also travels extra full cycles:

a + b + k(b + c)

So:

2(a + b) = a + b + k(b + c)

Therefore:

a + b = k(b + c)

Rearrange:

a = k(b + c) - b
a = (k - 1)(b + c) + c

This means:

distance from head to entry
equals
distance from meeting point to entry
mod cycle length

👉 Interview Answer

The cycle entry proof comes from distance relationships.

When slow and fast meet, fast has traveled twice as far as slow.

The difference between their distances is a multiple of the cycle length.

This implies that the distance from head to cycle entry equals the distance from the meeting point to the cycle entry modulo the cycle length.

So moving one pointer from head and one from the meeting point at the same speed makes them meet at the cycle entry.

🔟 Reorder List

Problem Pattern

Some linked list problems combine fast-slow pointer with reversal and merge.

Example:

1 → 2 → 3 → 4 → 5

Reorder into:

1 → 5 → 2 → 4 → 3

Steps

Use fast-slow pointer to find middle.
Reverse second half.
Merge first half and reversed second half.

Code

def reorder_list(head):
    if not head or not head.next:
        return

    # 1. Find middle
    slow = head
    fast = head

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

    # 2. Reverse second half
    second = slow.next
    slow.next = None

    prev = None
    while second:
        nxt = second.next
        second.next = prev
        prev = second
        second = nxt

    # 3. Merge
    first = head
    second = prev

    while second:
        temp1 = first.next
        temp2 = second.next

        first.next = second
        second.next = temp1

        first = temp1
        second = temp2

👉 Interview Answer

Reorder list is a good example where fast-slow pointer is only the first step.

I use fast-slow pointer to split the list into two halves.

Then I reverse the second half and merge the two halves alternately.

This keeps the solution O(n) time and O(1) extra space.

1️⃣1️⃣ Palindrome Linked List

Problem

Check whether a linked list is a palindrome.

1 → 2 → 2 → 1
true

Steps

Find the middle with fast-slow pointer.
Reverse the second half.
Compare both halves.

Code

def is_palindrome(head):
    if not head or not head.next:
        return True

    # 1. Find middle
    slow = head
    fast = head

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

    # 2. Reverse second half
    prev = None
    current = slow

    while current:
        nxt = current.next
        current.next = prev
        prev = current
        current = nxt

    # 3. Compare
    first = head
    second = prev

    while second:
        if first.val != second.val:
            return False

        first = first.next
        second = second.next

    return True

👉 Interview Answer

For palindrome linked list, I use fast-slow pointer to find the middle.

Then I reverse the second half of the list.

Finally, I compare the first half and reversed second half node by node.

This gives O(n) time and O(1) extra space.

1️⃣2️⃣ Happy Number

Problem

A happy number repeatedly replaces the number by the sum of squares of its digits.

If it eventually reaches 1, it is happy.

If it loops forever, it is not happy.

Example

19
1² + 9² = 82
8² + 2² = 68
6² + 8² = 100
1² + 0² + 0² = 1

So:

19 is happy

Cycle View

This creates a sequence:

n → next(n) → next(next(n)) → ...

If it does not reach 1, it eventually repeats.

That means:

there is a cycle

Code

def is_happy(n):
    def next_number(x):
        total = 0

        while x > 0:
            digit = x % 10
            total += digit * digit
            x //= 10

        return total

    slow = n
    fast = next_number(n)

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

    return fast == 1

👉 Interview Answer

Happy number can be modeled as cycle detection.

Each number points to the next number generated by summing the squares of its digits.

If the sequence reaches 1, the number is happy.

If it enters a cycle, it is not happy.

Therefore, fast and slow pointers can detect whether the sequence loops.

1️⃣3️⃣ Find Duplicate Number

Problem

Given an array of n + 1 integers where each integer is in the range 1 to n, find the duplicate number.

Key Constraint

nums length = n + 1
values range = 1 to n

This means each value can be treated as a pointer to another index.

index → nums[index]

Because there is a duplicate, there must be a cycle.

Code

def find_duplicate(nums):
    slow = nums[0]
    fast = nums[0]

    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]

        if slow == fast:
            break

    ptr1 = nums[0]
    ptr2 = slow

    while ptr1 != ptr2:
        ptr1 = nums[ptr1]
        ptr2 = nums[ptr2]

    return ptr1

Why It Works

Treat the array as a linked list:

index points to nums[index]

The duplicate value creates two paths into the same node, which forms a cycle.

👉 Interview Answer

Find Duplicate Number can be modeled as cycle detection.

Since values are in the range 1 to n, each value can point to another index.

The duplicate creates a cycle in this implicit linked list.

I use Floyd’s algorithm to find the cycle entry, which corresponds to the duplicate number.

1️⃣4️⃣ Fast & Slow Pointer vs Hash Set

Hash Set Approach

For cycle detection, we can use a set:

visited = set()

while head:
    if head in visited:
        return True

    visited.add(head)
    head = head.next

return False

Trade-Off

Approach	Time	Space	Notes
Hash Set	O(n)	O(n)	Easier to understand
Fast & Slow	O(n)	O(1)	Better space efficiency

👉 Interview Answer

A hash set can also detect cycles by storing visited nodes.

But it requires O(n) extra space.

Fast and slow pointer gives the same O(n) time complexity with O(1) space.

That is why it is preferred when constant space is required.

1️⃣5️⃣ When Fast & Slow Pointer Applies

Good Fit

Use fast and slow pointer when:

There is a linked structure.
There may be a cycle.
The sequence is deterministic.
Each state points to exactly one next state.
We need O(1) extra space.

Examples

Linked list cycle
Cycle entry point
Happy number
Find duplicate number
Middle of linked list
Palindrome linked list
Reorder list

👉 Interview Answer

Fast and slow pointer applies when the problem can be modeled as a sequence of states, where each state deterministically points to the next state.

If the sequence can repeat, then it forms a cycle.

This makes Floyd’s cycle detection a good fit.

1️⃣6️⃣ When Fast & Slow Pointer Does Not Apply

Not Good Fit

Fast and slow pointer is usually not suitable when:

The structure branches.
A state can have multiple next states.
The problem requires shortest path.
The problem requires exploring all possibilities.
The data is not a linked sequence.

Better Alternatives

Problem Type	Better Pattern
Graph with multiple neighbors	BFS / DFS
Shortest path	BFS / Dijkstra
Arbitrary duplicates	Hash Set
Sorted array pair search	Two Pointers
Contiguous subarray condition	Sliding Window

👉 Interview Answer

Fast and slow pointer works best for linear or cyclic sequences.

If each state can branch to multiple next states, then the problem is more like graph traversal.

In that case, BFS or DFS is usually more appropriate.

1️⃣7️⃣ Common Edge Cases

Empty List

head = None

Single Node Without Cycle

1 → null

Single Node With Cycle

1 ↘
↑__|

Two Nodes

1 → 2 → null

or:

1 → 2
↑   ↓
←___

Even vs Odd Length

Important for:

middle node
palindrome linked list
reorder list

👉 Interview Answer

The common edge cases are empty list, single node, single node with a cycle, two-node lists, and even versus odd length.

I pay special attention to loop conditions like fast and fast.next to avoid null pointer errors.

1️⃣8️⃣ Complexity Analysis

Cycle Detection

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

Find Middle

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

Cycle Entry

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

Happy Number

Time: O(log n) per transition, bounded by cycle behavior
Space: O(1)

Find Duplicate Number

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

👉 Interview Answer

Fast and slow pointer solutions are usually O(n) time and O(1) space.

The space benefit is the main advantage compared with hash-set based cycle detection.

Each pointer moves through the sequence a bounded number of times before either reaching the end or detecting a cycle.

1️⃣9️⃣ Common Mistakes

Mistake 1: Null Pointer Error

Wrong:

while fast:
    fast = fast.next.next

Correct:

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

Mistake 2: Returning Too Early

In cycle detection, compare after both pointers move.

slow = slow.next
fast = fast.next.next

if slow == fast:
    return True

Mistake 3: Confusing Meeting Point With Cycle Entry

The first meeting point is usually not the cycle entry.

You need the second phase:

one pointer from head
one pointer from meeting point
move both one step

Mistake 4: Middle Node Ambiguity

For even-length lists, clarify:

first middle or second middle?

Mistake 5: Applying It to Branching Graphs

Fast-slow pointer assumes a deterministic next state.

👉 Interview Answer

Common mistakes include missing null checks, confusing the meeting point with the cycle entry, using the wrong middle-node template, and applying fast-slow pointer to branching graphs.

I avoid these by defining what fast and slow represent and what condition terminates the loop.

2️⃣0️⃣ Standard Templates

Detect Cycle Template

def has_cycle(head):
    slow = head
    fast = head

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

        if slow == fast:
            return True

    return False

Find Middle Template

def middle_node(head):
    slow = head
    fast = head

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

    return slow

Find Cycle Entry Template

def detect_cycle(head):
    slow = head
    fast = head

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

        if slow == fast:
            ptr1 = head
            ptr2 = slow

            while ptr1 != ptr2:
                ptr1 = ptr1.next
                ptr2 = ptr2.next

            return ptr1

    return None

State Cycle Template

def has_state_cycle(start):
    def next_state(x):
        # compute next state
        pass

    slow = start
    fast = next_state(start)

    while slow != fast:
        slow = next_state(slow)
        fast = next_state(next_state(fast))

    return True

🧠 Staff-Level Answer Final

👉 Interview Answer Full Version

Fast and slow pointer is a two-pointer technique where two pointers move through a sequence at different speeds.

Usually, the slow pointer moves one step at a time, and the fast pointer moves two steps at a time.

This pattern is especially useful for linked lists and cycle detection.

The core idea is based on relative speed. If there is a cycle, the fast pointer gains one step on the slow pointer each iteration, so it must eventually meet the slow pointer inside the cycle.

If there is no cycle, the fast pointer reaches null.

The most classic application is Floyd’s cycle detection algorithm, also known as the tortoise and hare algorithm.

It detects whether a linked list has a cycle in O(n) time and O(1) space.

Fast and slow pointer can also find the middle of a linked list. Since fast moves twice as fast as slow, when fast reaches the end, slow is at the middle.

For even-length lists, I clarify whether the problem expects the first middle or the second middle, because the loop condition changes slightly.

For finding the cycle entry point, the first meeting point is not necessarily the entry. After slow and fast meet, I reset one pointer to the head and keep the other at the meeting point. Then I move both one step at a time. Their next meeting point is the cycle entry.

This works because the distance from head to cycle entry equals the distance from the meeting point to the entry modulo the cycle length.

Fast and slow pointer also applies beyond linked lists. Happy Number can be modeled as a sequence of numbers where each number points to the next number. If the sequence repeats, it forms a cycle.

Find Duplicate Number can also be modeled as an implicit linked list, where each index points to nums[index]. The duplicate creates a cycle, and the cycle entry corresponds to the duplicate value.

At a senior level, I would explain that this pattern works when the problem can be modeled as a deterministic sequence of states, where each state points to exactly one next state.

It is not appropriate for branching graphs or problems requiring exploration of multiple paths.

Compared with a hash set approach, fast and slow pointer gives the same O(n) time for cycle detection, but improves space from O(n) to O(1).

The main pitfalls are null pointer errors, confusing the first meeting point with the cycle entry, choosing the wrong middle-node template, and applying the pattern when the state transition is not deterministic.

⭐ Final Insight

Fast & Slow Pointer 的核心不是“一个快一个慢”。

它的核心是利用 relative speed 在 deterministic sequence 中发现结构信息。

Senior-level 的重点是：

sequence 是否 deterministic，是否可能形成 cycle， fast 为什么一定会追上 slow， meeting point 和 cycle entry 有什么区别，以及为什么这个方法可以做到 O(1) space。

能讲清楚这些， Fast & Slow Pointer 就不是 linked list 小技巧，而是一种 cycle detection 的通用思维模型。

中文部分

🎯 Fast & Slow Pointer

1️⃣ 核心框架

讨论 Fast & Slow Pointer 时，我通常从：

它解决什么问题
为什么速度差可以产生有用信息
Linked list cycle detection
找 linked list 中点
找 cycle entry point
Happy number
用 cycle logic 找 duplicate
常见 edge cases
Complexity analysis
高级工程师解释方式

2️⃣ 要解决什么问题？

Fast and slow pointer 是一种两个 pointer 以不同速度移动的技巧。

通常是：

slow pointer 每次走 1 步
fast pointer 每次走 2 步

它常用于：

Detecting cycles
Finding the middle of a linked list
Finding the entry point of a cycle
Checking whether a number sequence loops
Detecting duplicates in constrained arrays
Solving problems where repeated states imply a cycle

核心思想是：

如果存在 cycle，
快指针最终一定会追上慢指针。

👉 面试回答

Fast and slow pointer 是一种 two-pointer 技巧，其中一个 pointer 比另一个 pointer 移动更快。

它特别适合 linked list 和 cycle detection 问题。

如果存在 cycle，fast pointer 最终会遇到 slow pointer。

如果不存在 cycle，fast pointer 会到达链表结尾。

3️⃣ 为什么 Fast & Slow Pointer 有效？

基本直觉

想象两个跑步者在圆形跑道上：

slow runner: 每次走 1 步
fast runner: 每次走 2 步

如果跑道是圆的：

fast runner 最终会追上 slow runner

如果不是圆的：

fast runner 会到达终点

Linked List 视角

无环 linked list：

1 → 2 → 3 → 4 → null

有环 linked list：

1 → 2 → 3 → 4
        ↑     ↓
        6 ← 5

Fast pointer 要么：

到达 null

要么：

在 cycle 中遇到 slow pointer

👉 面试回答

Fast and slow pointer 有效的原因是 relative speed difference。

在 cycle 内部，fast 每一步都会相对 slow 多走一个节点。

因为 cycle 长度有限， fast 最终一定会追上 slow。

如果没有 cycle，fast 会直接走到 null。

4️⃣ Floyd’s Cycle Detection

又叫：

Tortoise and Hare Algorithm

slow pointer 是 tortoise。

fast pointer 是 hare。

Core Algorithm

slow = head
fast = head

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

    if slow == fast:
        return True

return False

Key Idea

如果 fast 追上 slow → 有 cycle
如果 fast 到达 null → 没有 cycle

👉 面试回答

Floyd’s cycle detection algorithm 使用两个不同速度的 pointer。

slow 每次走一步。

fast 每次走两步。

如果它们相遇，说明存在 cycle。

如果 fast 到达 null，说明不存在 cycle。

5️⃣ Linked List Cycle

Problem

给定 linked list 的 head，判断链表是否有 cycle。

Code

def has_cycle(head):
    slow = head
    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)

为什么是 O(n)？

如果没有 cycle：

fast 到达末尾

如果有 cycle：

fast 在 cycle 中遇到 slow

👉 面试回答

判断 linked list 是否有 cycle，我使用 fast and slow pointers。

slow 每次走一个节点。

fast 每次走两个节点。

如果链表有 cycle，fast 最终会遇到 slow。

如果 fast 到达 null，说明没有 cycle。

6️⃣ 找 Linked List 中点

Problem

给定 linked list，返回 middle node。

1 → 2 → 3 → 4 → 5
middle = 3

1 → 2 → 3 → 4 → 5 → 6
middle = 4

Code

def middle_node(head):
    slow = head
    fast = head

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

    return slow

为什么有效？

fast 的速度是 slow 的两倍：

fast 走 2x 距离
slow 走 1x 距离

所以当 fast 到结尾时：

slow 正好在中点

👉 面试回答

找 linked list 的中点，我使用 slow 和 fast pointers。

fast 每次走两步， slow 每次走一步。

当 fast 到达链表末尾时， slow 就在 middle node。

7️⃣ First Middle vs Second Middle

偶数长度链表

对于偶数长度：

1 → 2 → 3 → 4

有两个 middle candidates：

2 and 3

常见模板返回 second middle：

返回 Second Middle

def second_middle(head):
    slow = head
    fast = head

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

    return slow

返回 First Middle

def first_middle(head):
    slow = head
    fast = head

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

    return slow

👉 面试回答

对偶数长度 linked list，我会先确认题目需要 first middle 还是 second middle。

常见 slow-fast 模板返回 second middle。

如果需要 first middle，我会调整 loop condition，让 slow 提前停一个节点。

8️⃣ Linked List Cycle II

Problem

给定一个有 cycle 的 linked list，返回 cycle 开始的节点。

Algorithm

Step 1: 找 meeting point。

slow 和 fast 在 cycle 中相遇

Step 2: 一个 pointer 回到 head。

ptr1 = head
ptr2 = meeting point

Step 3: 两个 pointer 每次都走一步。

它们会在 cycle entry 相遇。

Code

def detect_cycle(head):
    slow = head
    fast = head

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

        if slow == fast:
            break
    else:
        return None

    ptr1 = head
    ptr2 = slow

    while ptr1 != ptr2:
        ptr1 = ptr1.next
        ptr2 = ptr2.next

    return ptr1

👉 面试回答

首先，我用 fast and slow pointers 判断是否有 cycle。

如果它们相遇，我把一个 pointer 放回 head，另一个 pointer 留在 meeting point。

然后两个 pointer 每次都走一步。

它们再次相遇的位置就是 cycle entry。

9️⃣ 为什么 Cycle Entry Logic 正确？

定义距离

设：

a = head 到 cycle entry 的距离
b = cycle entry 到 meeting point 的距离
c = meeting point 回到 cycle entry 的距离

Cycle length：

b + c

Slow 和 Fast 相遇时

Slow 走了：

a + b

Fast 走了：

2(a + b)

Fast 比 slow 多走了若干圈：

a + b + k(b + c)

所以：

2(a + b) = a + b + k(b + c)

因此：

a + b = k(b + c)

变形：

a = k(b + c) - b
a = (k - 1)(b + c) + c

这表示：

head 到 entry 的距离
等于
meeting point 到 entry 的距离，加上若干个完整 cycle

👉 面试回答

Cycle entry 的证明来自距离关系。

当 slow 和 fast 相遇时， fast 走过的距离是 slow 的两倍。

两者距离差一定是 cycle length 的整数倍。

这可以推出： head 到 cycle entry 的距离，等于 meeting point 到 cycle entry 的距离，mod cycle length。

所以一个 pointer 从 head 出发，一个 pointer 从 meeting point 出发，同速移动时会在 cycle entry 相遇。

🔟 Reorder List

Problem Pattern

有些 linked list 问题会把 fast-slow pointer 和 reverse、merge 结合起来。

例如：

1 → 2 → 3 → 4 → 5

重排成：

1 → 5 → 2 → 4 → 3

Steps

用 fast-slow pointer 找中点。
Reverse second half。
Merge first half and reversed second half。

Code

def reorder_list(head):
    if not head or not head.next:
        return

    # 1. Find middle
    slow = head
    fast = head

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

    # 2. Reverse second half
    second = slow.next
    slow.next = None

    prev = None
    while second:
        nxt = second.next
        second.next = prev
        prev = second
        second = nxt

    # 3. Merge
    first = head
    second = prev

    while second:
        temp1 = first.next
        temp2 = second.next

        first.next = second
        second.next = temp1

        first = temp1
        second = temp2

👉 面试回答

Reorder list 是 fast-slow pointer 和 linked list 操作结合的典型题。

我先用 fast-slow pointer 找到中点，把链表分成两半。

然后 reverse 第二半。

最后把两半交替 merge。

这样可以做到 O(n) time 和 O(1) extra space。

1️⃣1️⃣ Palindrome Linked List

Problem

判断 linked list 是否是 palindrome。

1 → 2 → 2 → 1
true

Steps

用 fast-slow pointer 找中点。
Reverse second half。
Compare both halves。

Code

def is_palindrome(head):
    if not head or not head.next:
        return True

    # 1. Find middle
    slow = head
    fast = head

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

    # 2. Reverse second half
    prev = None
    current = slow

    while current:
        nxt = current.next
        current.next = prev
        prev = current
        current = nxt

    # 3. Compare
    first = head
    second = prev

    while second:
        if first.val != second.val:
            return False

        first = first.next
        second = second.next

    return True

👉 面试回答

对 palindrome linked list，我先用 fast-slow pointer 找到中点。

然后 reverse 第二半链表。

最后逐个比较 first half 和 reversed second half。

这样可以做到 O(n) time 和 O(1) extra space。

1️⃣2️⃣ Happy Number

Problem

Happy number 会不断把数字替换成每位数字平方和。

如果最终变成 1，就是 happy number。

如果进入无限循环，就不是。

Example

19
1² + 9² = 82
8² + 2² = 68
6² + 8² = 100
1² + 0² + 0² = 1

所以：

19 is happy

Cycle View

这会形成一个 sequence：

n → next(n) → next(next(n)) → ...

如果不能到 1，就会重复。

这意味着：

存在 cycle

Code

def is_happy(n):
    def next_number(x):
        total = 0

        while x > 0:
            digit = x % 10
            total += digit * digit
            x //= 10

        return total

    slow = n
    fast = next_number(n)

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

    return fast == 1

👉 面试回答

Happy number 可以建模成 cycle detection。

每个数字通过 digit square sum 指向下一个数字。

如果 sequence 到达 1，说明是 happy。

如果 sequence 进入 cycle，说明不是 happy。

所以可以用 fast and slow pointer 判断是否循环。

1️⃣3️⃣ Find Duplicate Number

Problem

给定一个长度为 n + 1 的数组，其中每个整数都在 1 到 n 之间，找出 duplicate number。

Key Constraint

nums length = n + 1
values range = 1 to n

这说明每个 value 都可以被看作指向另一个 index 的 pointer。

index → nums[index]

因为有 duplicate，所以一定会形成 cycle。

Code

def find_duplicate(nums):
    slow = nums[0]
    fast = nums[0]

    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]

        if slow == fast:
            break

    ptr1 = nums[0]
    ptr2 = slow

    while ptr1 != ptr2:
        ptr1 = nums[ptr1]
        ptr2 = nums[ptr2]

    return ptr1

为什么有效？

把 array 看成 linked list：

index points to nums[index]

duplicate value 会让两个路径进入同一个节点，从而形成 cycle。

👉 面试回答

Find Duplicate Number 可以建模成 cycle detection。

因为 values 都在 1 到 n 之间，每个 value 都可以指向另一个 index。

Duplicate 会在这个 implicit linked list 中制造一个 cycle。

我使用 Floyd’s algorithm 找 cycle entry，这个 entry 就是 duplicate number。

1️⃣4️⃣ Fast & Slow Pointer vs Hash Set

Hash Set Approach

对于 cycle detection，可以用 set：

visited = set()

while head:
    if head in visited:
        return True

    visited.add(head)
    head = head.next

return False

Trade-Off

Approach	Time	Space	Notes
Hash Set	O(n)	O(n)	Easier to understand
Fast & Slow	O(n)	O(1)	Better space efficiency

👉 面试回答

Hash set 也可以用来检测 cycle，方法是记录访问过的 node。

但是它需要 O(n) extra space。

Fast and slow pointer 可以在同样 O(n) time 下，把 space 降到 O(1)。

所以当题目要求 constant space 时， fast-slow pointer 是更好的选择。

1️⃣5️⃣ 什么时候 Fast & Slow Pointer 适用？

Good Fit

当问题满足：

存在 linked structure
可能存在 cycle
sequence 是 deterministic
每个 state 只有一个 next state
需要 O(1) extra space

Examples

Linked list cycle
Cycle entry point
Happy number
Find duplicate number
Middle of linked list
Palindrome linked list
Reorder list

👉 面试回答

Fast and slow pointer 适用于可以被建模成 state sequence 的问题。

每个 state 都 deterministic 地指向下一个 state。

如果 sequence 可能重复，那就会形成 cycle。

这时 Floyd’s cycle detection 就很适合。

1️⃣6️⃣ 什么时候 Fast & Slow Pointer 不适用？

Not Good Fit

Fast and slow pointer 通常不适合：

结构会分叉
一个 state 有多个 next states
问题需要 shortest path
问题需要探索所有可能性
数据不是 linked sequence

Better Alternatives

Problem Type	Better Pattern
Graph with multiple neighbors	BFS / DFS
Shortest path	BFS / Dijkstra
Arbitrary duplicates	Hash Set
Sorted array pair search	Two Pointers
Contiguous subarray condition	Sliding Window

👉 面试回答

Fast and slow pointer 最适合 linear 或 cyclic sequence。

如果每个 state 可以走向多个 next states，那问题更像 graph traversal。

这时候 BFS 或 DFS 通常更合适。

1️⃣7️⃣ 常见 Edge Cases

Empty List

head = None

Single Node Without Cycle

1 → null

Single Node With Cycle

1 ↘
↑__|

Two Nodes

1 → 2 → null

或者：

1 → 2
↑   ↓
←___

Even vs Odd Length

对这些题很重要：

middle node
palindrome linked list
reorder list

👉 面试回答

常见 edge cases 包括 empty list、 single node、 single node with cycle、 two-node list、以及 even length 和 odd length。

我会特别注意 fast and fast.next 这种 loop condition，避免 null pointer error。

1️⃣8️⃣ Complexity Analysis

Cycle Detection

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

Find Middle

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

Cycle Entry

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

Happy Number

Time: O(log n) per transition, bounded by cycle behavior
Space: O(1)

Find Duplicate Number

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

👉 面试回答

Fast and slow pointer 通常是 O(n) time 和 O(1) space。

相比 hash set cycle detection，它最大的优势是节省空间。

每个 pointer 在 detection 完成前，都只会在 sequence 中移动有限次数。

1️⃣9️⃣ 常见错误

Mistake 1: Null Pointer Error

错误：

while fast:
    fast = fast.next.next

正确：

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

Mistake 2: 过早比较

Cycle detection 中通常先移动，再比较：

slow = slow.next
fast = fast.next.next

if slow == fast:
    return True

Mistake 3: 把 Meeting Point 当成 Cycle Entry

第一次相遇点通常不是 cycle entry。

还需要第二阶段：

一个 pointer 从 head 出发
一个 pointer 从 meeting point 出发
两个都每次走一步

Mistake 4: Middle Node Ambiguity

偶数长度时要确认：

first middle or second middle?

Mistake 5: 用在 Branching Graph 上

Fast-slow pointer 假设每个 state 只有一个 deterministic next state。

👉 面试回答

常见错误包括 null check 不完整、把 meeting point 当成 cycle entry、 middle node 模板选错、以及把 fast-slow pointer 用在 branching graph 上。

我通常会先定义 fast 和 slow 分别表示什么，以及 loop 的终止条件是什么。

2️⃣0️⃣ 标准模板

Detect Cycle Template

def has_cycle(head):
    slow = head
    fast = head

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

        if slow == fast:
            return True

    return False

Find Middle Template

def middle_node(head):
    slow = head
    fast = head

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

    return slow

Find Cycle Entry Template

def detect_cycle(head):
    slow = head
    fast = head

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

        if slow == fast:
            ptr1 = head
            ptr2 = slow

            while ptr1 != ptr2:
                ptr1 = ptr1.next
                ptr2 = ptr2.next

            return ptr1

    return None

State Cycle Template

def has_state_cycle(start):
    def next_state(x):
        # compute next state
        pass

    slow = start
    fast = next_state(start)

    while slow != fast:
        slow = next_state(slow)
        fast = next_state(next_state(fast))

    return True

🧠 Staff-Level Answer Final

👉 面试回答完整版本

Fast and slow pointer 是一种 two-pointer technique，两个 pointer 在 sequence 中以不同速度移动。

通常 slow pointer 每次走一步， fast pointer 每次走两步。

这个 pattern 特别适合 linked list 和 cycle detection。

它的核心来自 relative speed。如果存在 cycle， fast pointer 每次都会相对 slow pointer 多前进一个节点，所以最终一定会在 cycle 中追上 slow pointer。

如果不存在 cycle， fast pointer 会到达 null。

最经典的应用是 Floyd’s cycle detection algorithm，也叫 tortoise and hare algorithm。

它可以在 O(n) time 和 O(1) space 内判断 linked list 是否有 cycle。

Fast and slow pointer 也可以用来找 linked list 的 middle。因为 fast 的速度是 slow 的两倍，所以当 fast 到达末尾时， slow 正好在中点。

对偶数长度 linked list，我会确认题目要 first middle 还是 second middle，因为 loop condition 会略有不同。

对 cycle entry point，第一次 meeting point 不一定是 cycle entry。当 slow 和 fast 相遇后，我把一个 pointer 放回 head，另一个 pointer 留在 meeting point。然后两个 pointer 同速移动。它们再次相遇的位置就是 cycle entry。

这个结论来自距离关系： head 到 cycle entry 的距离，等于 meeting point 到 cycle entry 的距离，mod cycle length。

Fast and slow pointer 也可以用于 linked list 之外的问题。 Happy Number 可以看成一个数字 sequence，每个数字通过 digit square sum 指向下一个数字。如果 sequence 重复，就形成 cycle。

Find Duplicate Number 也可以建模成 implicit linked list。每个 index 指向 nums[index]。 Duplicate value 会制造 cycle， cycle entry 就对应 duplicate number。

高级工程师层面，我会解释这个 pattern 适用于 deterministic sequence：每个 state 只能指向一个 next state。

如果问题是 branching graph，或者需要探索多条路径，那 fast-slow pointer 就不合适，应该考虑 BFS、DFS 或其他 graph algorithms。

相比 hash set， fast-slow pointer 在 cycle detection 中同样是 O(n) time，但可以把 space 从 O(n) 降到 O(1)。

主要陷阱是 null pointer error、混淆 meeting point 和 cycle entry、 middle-node 模板选择错误，以及在非 deterministic structure 上误用这个 pattern。

⭐ Final Insight

Fast & Slow Pointer 的核心不是“快慢两个指针”。

它的核心是用 relative speed 发现 deterministic sequence 中的 cycle 或结构位置。

Senior-level 的重点是：

sequence 是否 deterministic，是否可能形成 cycle， fast 为什么一定会追上 slow， meeting point 和 cycle entry 为什么不同，以及为什么这个方法能做到 O(1) space。

能讲清楚这些， Fast & Slow Pointer 就是一种通用的 cycle detection 思维模型。