Разворот связного списка

O(n)

Пройди список один раз, и на каждом узле переверни указатель .next так, чтобы он указывал назад, а не вперёд, неся с собой prev/curr/next, чтобы ничего не потерять.

Сигналы

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

Шаблон

function reverseList(head) {
    let prev = null;
    let curr = head;
    while (curr) {
        const next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

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

Два указателя (в одну сторону): Указатели в одну сторону идут по индексам массива: один быстро читает, другой медленно пишет. У разворота нет ни массива, ни индексов; он перепрошивает поле .next у каждого узла на месте, это хирургия указателей, а не обход по индексам.

n до 1e5 узлов -> O(n): один проход, у каждого узла указатель меняется один раз, O(1) доп. памяти.

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