MidПрактика10 min

Паттерны: Fast & Slow Pointers

Обнаружение цикла, поиск середины, проверка палиндрома в связных списках

AlgoLinked lists

Паттерны: Fast & Slow Pointers

Идея паттерна

Fast & Slow Pointers (Черепаха и Заяц) — два указателя двигаются с разной скоростью: slow на 1 шаг, fast на 2. Это позволяет решать задачи на циклы, середину и структуру списка.

slow:  o . o . o . o . o
fast:  o . . o . . o . . o

Если есть цикл — fast догонит slow.
Если нет цикла — fast дойдёт до конца.

Задача 1: Обнаружение цикла (Floyd's Algorithm)

function hasCycle(?ListNode $head): bool
{
    $slow = $head;
    $fast = $head;

    while ($fast !== null && $fast->next !== null) {
        $slow = $slow->next;          // 1 step
        $fast = $fast->next->next;    // 2 steps

        if ($slow === $fast) {
            return true;
        }
    }

    return false; // fast reached the end — no cycle
}
Визуализация: 
Список с циклом:
1 -> 2 -> 3 -> 4 -> 5
               ^         |
               |         v
               8 <- 7 <- 6

Шаг 0: slow=1, fast=1
Шаг 1: slow=2, fast=3
Шаг 2: slow=3, fast=5
Шаг 3: slow=4, fast=7
Шаг 4: slow=5, fast=3  (fast уже в цикле)
Шаг 5: slow=6, fast=5
Шаг 6: slow=7, fast=7  <- ВСТРЕТИЛИСЬ!

Почему это работает?

Когда оба указателя внутри цикла длины C:

  • Расстояние между ними уменьшается на 1 каждый шаг
  • Значит, за максимум C шагов они встретятся

Задача 2: Найти начало цикла

После обнаружения цикла: перемещаем один указатель на head, оба двигаются по 1 шагу.

function detectCycleStart(?ListNode $head): ?ListNode
{
    $slow = $head;
    $fast = $head;

    // Step 1: Find meeting point
    while ($fast !== null && $fast->next !== null) {
        $slow = $slow->next;
        $fast = $fast->next->next;
        if ($slow === $fast) {
            // Found cycle, now find start
            $slow = $head;
            while ($slow !== $fast) {
                $slow = $slow->next;
                $fast = $fast->next; // Both 1 step!
            }
            return $slow; // Start of cycle
        }
    }

    return null; // No cycle
}
### Математическое доказательство 
head          start
  |             |
  v             v
  o--o--o--o--o--o--o--o
  |<-- a -->|  |        |
                |<- c ->|
                |        |
                o--o--o--o
                |<- b ->|

a = расстояние от head до начала цикла
b = расстояние от начала цикла до точки встречи
C = длина цикла

При встрече:
  slow прошёл: a + b
  fast прошёл: a + b + k*C (k полных кругов)
  fast = 2 * slow:
  a + b + k*C = 2(a + b)
  k*C = a + b
  a = k*C - b

Значит: если идти a шагов от head и от точки встречи —
оба окажутся в начале цикла!

Задача 3: Поиск середины списка

function findMiddle(?ListNode $head): ?ListNode
{
    $slow = $head;
    $fast = $head;

    while ($fast !== null && $fast->next !== null) {
        $slow = $slow->next;
        $fast = $fast->next->next;
    }

    return $slow;
}

// Odd count: 1->2->3->4->5
// slow: 1, 2, 3    fast: 1, 3, 5
// Middle: 3

// Even count: 1->2->3->4
// slow: 1, 2, 3    fast: 1, 3, null
// Returns 3 (second middle)
Если нужна **первая** середина для чётного: 
function findMiddleFirst(?ListNode $head): ?ListNode
{
    $slow = $head;
    $fast = $head;

    while ($fast->next !== null && $fast->next->next !== null) {
        $slow = $slow->next;
        $fast = $fast->next->next;
    }

    return $slow;
}

// 1->2->3->4
// slow: 1, 2    fast: 1, 3
// Returns 2 (first middle)
## Задача 4: Палиндром в связном списке

Алгоритм:

  1. Найти середину (fast/slow)
  2. Развернуть вторую половину
  3. Сравнить обе половины
function isPalindromeList(?ListNode $head): bool
{
    if ($head === null || $head->next === null) {
        return true;
    }

    // 1. Find middle
    $slow = $head;
    $fast = $head;
    while ($fast->next !== null && $fast->next->next !== null) {
        $slow = $slow->next;
        $fast = $fast->next->next;
    }

    // 2. Reverse second half
    $secondHalf = reverseList($slow->next);

    // 3. Compare
    $firstHalf = $head;
    while ($secondHalf !== null) {
        if ($firstHalf->val !== $secondHalf->val) {
            return false;
        }
        $firstHalf = $firstHalf->next;
        $secondHalf = $secondHalf->next;
    }

    return true;
}

function reverseList(?ListNode $head): ?ListNode
{
    $prev = null;
    while ($head !== null) {
        $next = $head->next;
        $head->next = $prev;
        $prev = $head;
        $head = $next;
    }
    return $prev;
}
Визуализация для `1 -> 2 -> 3 -> 2 -> 1`: 
Шаг 1: Середина = 3
1 -> 2 -> 3 -> 2 -> 1

Шаг 2: Разворачиваем после середины
1 -> 2 -> 3    1 -> 2

Шаг 3: Сравниваем
1 == 1 ✓
2 == 2 ✓
Палиндром!

Задача 5: Удаление n-го с конца

function removeNthFromEnd(?ListNode $head, int $n): ?ListNode
{
    $dummy = new ListNode(0);
    $dummy->next = $head;
    $fast = $dummy;
    $slow = $dummy;

    // Fast is ahead of slow by n+1 steps
    for ($i = 0; $i <= $n; $i++) {
        $fast = $fast->next;
    }

    // Move both until fast reaches the end
    while ($fast !== null) {
        $slow = $slow->next;
        $fast = $fast->next;
    }

    // slow->next is the target node
    $slow->next = $slow->next->next;

    return $dummy->next;
}

// Remove 2nd from end in [1, 2, 3, 4, 5]
// fast ahead by n+1=3 steps: fast=3
// Move: slow=1,fast=4 -> slow=2,fast=5 -> slow=3,fast=null
// slow->next = 4 (remove)
// Result: [1, 2, 3, 5]
## Задача 6: Пересечение двух списков 
function getIntersection(?ListNode $headA, ?ListNode $headB): ?ListNode
{
    if ($headA === null || $headB === null) {
        return null;
    }

    $a = $headA;
    $b = $headB;

    // When a reaches the end — switch to headB
    // When b reaches the end — switch to headA
    // They will meet at the intersection (or both become null)
    while ($a !== $b) {
        $a = ($a !== null) ? $a->next : $headB;
        $b = ($b !== null) ? $b->next : $headA;
    }

    return $a; // Intersection point or null
}
``` Список A: 1 -> 2 -> | +--> 8 -> 9 -> null Список B: 3 -> 4 -> 5 -> |

a: 1, 2, 8, 9, null, 3, 4, 5, 8 b: 3, 4, 5, 8, 9, null, 1, 2, 8 ^ встретились на 8!

Почему работает: len(A) + len(B) = len(B) + len(A) Оба пройдут одинаковое расстояние до точки пересечения.


## Сводная таблица паттернов

| Задача                   | Подход            | Сложность       |
|--------------------------|-------------------|-----------------|
| Обнаружение цикла        | Fast/Slow         | O(n) / O(1)     |
| Начало цикла             | Fast/Slow + reset | O(n) / O(1)     |
| Середина списка          | Fast/Slow         | O(n) / O(1)     |
| Палиндром                | Середина + reverse| O(n) / O(1)     |
| N-й с конца              | Fast ahead by n   | O(n) / O(1)     |
| Пересечение              | Two pointer switch| O(n+m) / O(1)   |

> **Запомни:** Fast & Slow — это не просто про связные списки. Этот паттерн применяется для: обнаружения циклов в любых последовательностях, нахождения дубликатов (Floyd's для массивов), определения структурных свойств (середина, длина). На интервью: если задача про связный список — первым делом подумай о двух указателях.

## Итоги

1. Fast (2 шага) + Slow (1 шаг) = обнаружение цикла
2. Reset к head после встречи = начало цикла
3. Когда fast дошёл до конца, slow на середине
4. Палиндром = середина + разворот + сравнение
5. N-й с конца = опережение fast на n шагов
6. Все задачи решаются за O(n) времени и O(1) памяти

Проверь себя

Как проверить, является ли связный список палиндромом, используя O(1) дополнительной памяти?

После обнаружения цикла в алгоритме Флойда, как найти НАЧАЛО цикла?

В задаче «удалить n-й элемент с конца» списка, зачем fast опережает slow на n+1 шагов, а не на n?

Для списка 1->2->3->4->5, где окажется slow-указатель когда fast дойдёт до конца?

В алгоритме Флойда для обнаружения цикла, почему fast двигается именно на 2 шага, а не на 3?