Алгоритм Флойда «черепаха і заєць» для пошуку циклу в зв'язному списку

Маємо зв'язний список, початок якого позначено як head, і в якому цикл може бути присутнім, а може й ні. Наприклад:

Тут нам потрібно знайти точку C, тобто початок циклу.

Коли підходить цей алгоритм?

• Чи структура задає функціональний перехід — з кожного стану рівно один наступний (зв'язний список, ітерація $x \to f(x)$)?
• Чи потрібно виявити цикл, використовуючи $O(1)$ пам'яті, без множини відвіданих вершин?
• Чи потрібно знайти саме початок циклу, а не лише факт його наявності?

Запропонований алгоритм

Цей алгоритм називається алгоритмом Флойда для пошуку циклу, або алгоритмом «черепаха і заєць». Щоб з'ясувати початок циклу, спершу нам потрібно зрозуміти, чи цикл узагалі існує. Це складається з двох кроків:

1. Визначити наявність циклу.
2. Знайти початок циклу.

Крок 1: наявність циклу

1. Візьмемо два вказівники, $slow$ і $fast$.
2. Спочатку обидва вказуватимуть на head зв'язного списку.
3. $slow$ рухатиметься на один крок за раз.
4. $fast$ рухатиметься на два кроки за раз (удвічі швидше за вказівник $slow$).
5. Перевіряємо, чи в якийсь момент вони вкажуть на одну й ту саму вершину, перш ніж один із них (або обидва) досягне null.
6. Якщо в якийсь момент свого шляху вони вказують на одну й ту саму вершину, це означає, що цикл у зв'язному списку справді існує.
7. Якщо ж ми отримуємо null, це означає, що зв'язний список не містить циклу.

Тепер, коли ми з'ясували, чи присутній цикл у зв'язному списку, на наступному кроці нам потрібно знайти початок циклу, тобто C.

Крок 2: початок циклу

1. Скинемо вказівник $slow$ на head зв'язного списку.
2. Рухаємо обидва вказівники на один крок за раз.
3. Точка, у якій вони зустрінуться, і буде початком циклу.

// Наявність циклу
public boolean hasCycle(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;

    while(fast != null && fast.next != null){
        slow = slow.next;
        fast = fast.next.next;
        if(slow==fast){
            return true;
        }
    }

    return false;
}

// Припускаємо, що цикл присутній і slow та fast вказують на точку своєї зустрічі
slow = head;
while(slow!=fast){
	slow = slow.next;
	fast = fast.next;
}

return slow; // початок циклу.

Чому це працює

Крок 1: наявність циклу

Оскільки вказівник $fast$ рухається удвічі швидше за $slow$, можна сказати, що в будь-який момент часу $fast$ пройшов би удвічі більшу відстань, ніж $slow$. Також можна вивести, що різниця між відстанями, які пройшли обидва вказівники, зростає на $1$.

slow: 0 --> 1 --> 2 --> 3 --> 4 (пройдена відстань)
fast: 0 --> 2 --> 4 --> 6 --> 8 (пройдена відстань)
diff: 0 --> 1 --> 2 --> 3 --> 4 (різниця між пройденими обома вказівниками відстанями)

Нехай $L$ позначає довжину циклу, а $a$ — кількість кроків, потрібних повільному вказівнику, щоб дістатися входу в цикл. Існує таке додатне ціле число $k$ ($k > 0$), що $k \cdot L \geq a$. Коли повільний вказівник пройшов $k \cdot L$ кроків, а швидкий вказівник подолав $2 \cdot k \cdot L$ кроків, обидва вказівники опиняються всередині циклу. У цей момент між ними відстань $k \cdot L$. Оскільки довжина циклу дорівнює $L$, це означає, що вони перебувають в одній і тій самій точці циклу, тобто зустрічаються.

Крок 2: початок циклу

Спробуймо обчислити відстань, яку пройшли обидва вказівники до моменту їхньої зустрічі всередині циклу.

$slowDist = a + xL + b$ , $x\ge0$

$fastDist = a + yL + b$ , $y\ge0$

• $slowDist$ — це загальна відстань, яку пройшов повільний вказівник.
• $fastDist$ — це загальна відстань, яку пройшов швидкий вказівник.
• $a$ — це кількість кроків, які обом вказівникам потрібно зробити, щоб увійти в цикл.
• $b$ — це відстань між C і G, тобто відстань між початком циклу та точкою зустрічі обох вказівників.
• $x$ — це кількість разів, що повільний вказівник зробив повний оберт усередині циклу, починаючи й закінчуючи в C.
• $y$ — це кількість разів, що швидкий вказівник зробив повний оберт усередині циклу, починаючи й закінчуючи в C.

$fastDist = 2 \cdot (slowDist)$

$a + yL + b = 2(a + xL + b)$

Розв'язавши формулу, отримуємо:

$a=(y-2x)L-b$

де $y-2x$ — ціле число

По суті, це означає, що $a$ кроків — це те саме, що зробити деяку кількість повних обертів у циклі та пройти $b$ кроків назад. Оскільки швидкий вказівник уже на $b$ кроків випереджає вхід у цикл, то, якщо він зробить ще $a$ кроків, він опиниться на вході в цикл. А оскільки ми поставили повільний вказівник на початок зв'язного списку, то після $a$ кроків він також опиниться на вході в цикл. Отже, якщо обидва пройдуть $a$ кроків, вони обидва зустрінуться на вході в цикл.

Задачі:

• Linked List Cycle (EASY)
• Happy Number (Easy)
• Find the Duplicate Number (Medium)
• Linked List Cycle II

Відеоматеріали