MiddleКодОчень частоЕщё не отвечали
Найдите зацикливание в односвязном списке
Дана голова односвязного списка. Верните true, если в списке есть цикл, и false в противном случае.
Требования:
хеш-множества посещённых узлов.
перед продвижением быстрого указателя (нужно для списков чётной длины).
- O(n) время, O(1) дополнительной памяти — без вспомогательного
- Защита от разыменования nullptr: проверяйте и
fast, иfast->next
struct Node {
int val;
Node* next;
};
bool hasCycle(Node* head) {
// ваш код здесь
}Допишите реализацию.
Алгоритм Флойда (черепаха и заяц) использует два указателя от головы, движущихся с разной скоростью: медленный — на 1 шаг за итерацию, быстрый — на 2; если они встретились внутри списка, цикл есть, а если быстрый дошёл до nullptr — цикла нет. Время O(n), память O(1).
- ✗Использовать хеш-множество для отслеживания посещённых узлов — O(n) память, не нужна с алгоритмом Флойда
- ✗Не проверять
fast && fast->nextперед продвижением — приводит к разыменованию nullptr - ✗Останавливаться на fast == nullptr, но не проверять fast->next == nullptr (нужно для списков чётной длины)
- →Как найти начало цикла после его обнаружения?
- →Как найти длину цикла?
Оглавление
Задача
Напишите функцию, определяющую, есть ли цикл в односвязном списке. Бонус: найти начало цикла.
Решение
#include <cassert>
struct Node {
int val;
Node* next;
explicit Node(int v, Node* n = nullptr) : val(v), next(n) {}
};
// Алгоритм Флойда — O(n) время, O(1) память
bool hasCycle(Node* head) {
Node* slow = head;
Node* fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) return true;
}
return false;
}
// Найти начало цикла (возвращает nullptr если цикла нет)
Node* findCycleStart(Node* head) {
Node* slow = head;
Node* fast = head;
// Шаг 1: обнаружить встречу
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) break;
}
if (!fast || !fast->next) return nullptr; // нет цикла
// Шаг 2: переставить slow на голову, двигать оба по 1 шагу
slow = head;
while (slow != fast) {
slow = slow->next;
fast = fast->next;
}
return slow; // начало цикла
}
int main() {
// Список без цикла: 1 -> 2 -> 3 -> nullptr
Node* list = new Node(1, new Node(2, new Node(3)));
assert(!hasCycle(list));
// Список с циклом: 1 -> 2 -> 3 -> 4 -> (назад к 2)
Node* n1 = new Node(1);
Node* n2 = new Node(2);
Node* n3 = new Node(3);
Node* n4 = new Node(4);
n1->next = n2; n2->next = n3; n3->next = n4; n4->next = n2;
assert(hasCycle(n1));
assert(findCycleStart(n1) == n2); // цикл начинается с n2
}Ключевые моменты
- Алгоритм Флойда: O(n) время, O(1) память — оптимально.
- Hash-set подход: O(n) время, O(n) память — проще понять, но хуже.
- Нахождение начала цикла: после встречи переставить один указатель на head и двигать оба по 1 — встретятся в начале цикла (математическое доказательство через расстояния).
Оглавление
