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

Разворот связного списка: как это работает?

Держите три ссылки: предыдущий узел, текущий и следующий за текущим. Предыдущий начинается с null.

Сохраните current.next до того, как что-то менять. Иначе остаток списка потеряется.

Направьте current.next на предыдущий узел. Эта одна строка и есть разворот.

Сдвиньте предыдущий на текущий, а текущий на сохранённый узел. Окно продвинулось на один шаг.

Остановитесь, когда текущий стал null. Предыдущий теперь указывает на бывший последний узел.

Верните предыдущий, а не текущий. Бывшая голова стала хвостом.

1. prev = null, cur = 1Список читается как 1, 2, 3. Пока ничего не развёрнуто.
2. 1 указывает на null, cur = 2Узел 1 теперь смотрит в null. Он стал хвостом.
3. 2 указывает на 1, cur = 3Узел 2 смотрит назад на узел 1. Два узла готовы.
4. 3 указывает на 2, cur = nullПоследний узел развернулся. Текущий ушёл за конец.
5. голова = 3В prev лежит новая голова. Три разворота за один проход.

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

Разворот связного списка: разбор примера

Развернуть только часть списка

Разверните узлы с позиции left по позицию right. Всё вне этого диапазона сохраняет порядок.

Ожидается один проход, копировать значения нельзя.

Дойдите до узла перед left и удержите его. Назовём этот узел якорем.

Потом перетаскивайте каждый следующий узел в начало развёрнутой части. Якорь держит список связным.

function reverseBetween(head, left, right) {
    const dummy = new ListNode(0, head);

    let anchor = dummy;
    for (let i = 1; i < left; i++) anchor = anchor.next;

    const tail = anchor.next; // this node ends up last in the reversed part

    for (let i = 0; i < right - left; i++) {
        const moved = tail.next;
        tail.next = moved.next;
        moved.next = anchor.next;
        anchor.next = moved;
    }

    return dummy.next;
}

Разворот связного списка: когда применять?

Эти формулировки в условии ведут сюда:

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

Разворот связного списка: с чем путают?

• Слияние и перестройка связного списка (Linked list merge & reorder): Слияние сплетает два списка в один. Разворот перевязывает один список на месте.
• Быстрый и медленный указатели (Fast & slow pointers): Та пара находит середину или цикл обходом. Она не меняет ни одной ссылки.
• Стек (LIFO) (Stack (LIFO)): Сложить все узлы в стек и снять их тоже даёт разворот. Это стоит O(n) памяти.
• Рекурсия (Recursion): Рекурсивный вариант читается хорошо, но тратит n кадров стека. Цикл обходится тремя переменными.

Разворот связного списка: частые ошибки

• Теряют остаток списка

  Перезапись current.next без сохранения выбрасывает все последующие узлы. Сохраняйте ссылку заранее.

• Возвращают не тот узел

  После цикла текущий равен null. Новая голова это предыдущий.

• Оставляют старую голову висеть

  Она обязана в итоге смотреть в null. Старт предыдущего с null даёт это бесплатно.

• Берут рекурсию на длинном списке

  Миллион узлов означает миллион кадров стека. Это переполняет стек вызовов.

Разворот связного списка: задачи с собеседований

• Разворот связного списка: Чистая форма на трёх переменных.
• Разворот связного списка II: Разворачивается только участок, поэтому нужен якорь.
• Разворот узлов группами по k: Разверните каждый блок из k, потом соедините блоки.
• Палиндром в связном списке: Разверните вторую половину и сравните с первой.
• Перестройка списка: Разрежьте, разверните заднюю половину и сплетите обе.
• Обмен узлов парами: Разворот, где k равно двум.
• Сложение двух чисел II: Разверните оба списка, сложите и разверните результат.

Разворот связного списка: сложность по времени и памяти

O(n)

n до 1e6 даёт O(n) времени и O(1) памяти. Рекурсивная форма стоит O(n) стека.