141. Linked List Cycle

Задача

Дан head (голова) связного списка. Определите, есть ли в этом списке цикл.

Цикл в связном списке существует, если в списке есть узел, до которого можно снова добраться, непрерывно следуя по указателю next. Внутренне pos используется для обозначения индекса узла, к которому подключён указатель next хвоста (tail). Обратите внимание, что pos не передаётся в качестве параметра.

Верните true, если в связном списке есть цикл. В противном случае верните false.

Примеры

Пример 1

Input: head = [3,2,0,-4], pos = 1
Output: true

Пояснение

В связном списке есть цикл, где хвост соединяется с 1-м узлом (индексация с 0).

Пример 2

Input: head = [1,2], pos = 0
Output: true

Пояснение

В связном списке есть цикл, где хвост соединяется с 0-м узлом.

Пример 3

Input: head = [1], pos = -1
Output: false

Пояснение

В связном списке нет цикла.

Решение

Подсказка

Представь, что два бегуна бегут по стадиону.
Один бежит медленно (шаг за шагом), а другой быстро (через шаг).
 
Если стадион — это кольцо (цикл), то что неизбежно произойдет с быстрым и медленным бегуном через какое-то время?
А если это не кольцо, а прямая дорога, что случится с быстрым бегуном?

Решение 1 (алгоритм "Черепаха и Заяц" или алгоритм Флойда)

// Временная сложность: O(N) — если цикла нет, пройдем весь список. Если цикл есть, "быстрый" догонит "медленного" за O(N) шагов.
// Пространственная сложность: O(1) — используем только два указателя, никакой дополнительной памяти.
 
var hasCycle = function(head) {
    if (!head?.next) return false;
 
    let slow = head;
    let fast = head.next;
 
    while (fast && fast.next) {
        if (slow === fast) return true;
 
        slow = slow.next;
        fast = fast.next.next;
    }
 
    return false;
};

Решение 2 (Set)

// Временная сложность: O(N)
// Пространственная сложность: O(N) — храним ссылки на все узлы
 
var hasCycle = function(head) {
    const visited = new Set();
 
    while (head) {
        if (visited.has(head)) return true;
        visited.add(head);
        head = head.next;
    }
 
    return false;
};

Решение 3 (Modifying Inputs)

// Временная сложность: O(N)
// Пространственная сложность: O(1)
 
var hasCycle = function(head) {
    while (head) {
        if (head.seen) return true; // Узел уже посещали
        head.seen = true;           // Ставим метку
        head = head.next;
    }
    return false;
};