Быстрый и медленный указатели

O(n)

Пусти два указателя от головы списка: медленный на один шаг, быстрый на два шага за раз. Если есть цикл, они рано или поздно встретятся; если цикла нет, быстрый первым дойдёт до конца. Точка встречи также даёт средний узел.

Сигналы

обнаружить цикл в связном спискенайти, где начинается циклнайти средний узел спискаопределить, является ли список палиндромомбез доп. памяти / O(1) память, только указатели

Шаблон

function hasCycle(head) {
    let slow = head;
    let fast = head;
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow === fast) return true;
    }
    return false;
}

Похоже, но не то

Два указателя (с концов): Указатели с концов стартуют с обоих концов массива и сходятся навстречу друг другу. Быстрый/медленный оба стартуют с головы списка и идут вперёд с разной скоростью; у односвязного списка нет «другого конца», откуда можно было бы сходиться.

n до 1e5 узлов -> O(n): быстрый указатель проходит не более 2n шагов до встречи с медленным или конца списка.

Изучить этот паттерн