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

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

Держите три ссылки: предыдущий узел, текущий и следующий за текущим. Предыдущий начинается с 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;
}

interface ListNode {
    val: number;
    next: ListNode | null;
}

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

def reverse_list(head):
    prev = None
    curr = head
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    return prev

function reverseList(?Node $head): ?Node {
    $prev = null;
    $curr = $head;
    while ($curr !== null) {
        $next = $curr->next;
        $curr->next = $prev;
        $prev = $curr;
        $curr = $next;
    }
    return $prev;
}

    public static ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }

    public static class ListNode {
        public int val;
        public ListNode next;
    }

    public static ListNode ReverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }

    public class ListNode {
        public int val;
        public ListNode next;
    }

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

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

Разверните узлы с позиции 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) доп. памяти». Решение на нём обычно укладывается в O(n).

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

Слова в условии для всех паттернов собраны в одной таблице: шпаргалка по паттернам алгоритмов.

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

Паттерн «Разворот связного списка» чаще всего путают с этими паттернами: Слияние и перестройка связного списка, Быстрый и медленный указатели, Стек (LIFO) и Рекурсия.

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

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

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

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

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

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

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

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

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

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

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

Паттерн «Разворот связного списка» решает такие задачи с собеседований: Разворот связного списка, Разворот связного списка II, Разворот узлов группами по k, Палиндром в связном списке, Перестройка списка, Обмен узлов парами и Сложение двух чисел II.

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

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

У паттерна «Разворот связного списка» целевая сложность O(n).

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