Premium

Связные списки

Разворот списка

Развернуть односвязный список на месте

Легкий

Постановка задачи

Описание (LeetCode - 206. Reverse Linked List)

Дана голова односвязного списка head. Нужно развернуть список и вернуть новую голову.

Пример 1:

head = [1, 2, 3, 4, 5]

Результат:

[5, 4, 3, 2, 1]

Пример 2:

head = [1, 2]

Результат:

[2, 1]

Пример 3:

head = []

Результат:

[]

Ограничения:

  • Количество узлов в списке от 0 до 5000
  • -5000 <= Node.val <= 5000

Решение

Разворот связного списка - базовая задача на работу с указателями. Мы не можем просто пройтись по индексам, как в массиве. Нужно менять ссылки next у самих узлов.

Идея решения:

Будем идти по списку слева направо и постепенно разворачивать уже пройденную часть.

Нам нужны три указателя:

  1. previous - голова уже развернутой части.
  2. current - узел, который мы обрабатываем сейчас.
  3. next - следующий узел, который нужно сохранить перед изменением ссылки.

На каждом шаге мы меняем направление стрелки:

current.next = previous;

После этого сдвигаем previous и current.

Основные шаги:

  1. Инициализируем previous = null, current = head.
  2. Пока current не равен null:
    • сохраняем next = current.next;
    • направляем current.next на previous;
    • сдвигаем previous = current;
    • сдвигаем current = next.
  3. Когда цикл завершится, previous будет новой головой списка.

Рассмотрим список:

1 -> 2 -> 3 -> null

После инициализации:

previous -> null
current -> 1 -> 2 -> 3 -> null

После первого шага цикла:

previous -> 1 -> null
current -> 2 -> 3 -> null

После второго:

previous -> 2 -> 1 -> null
current -> 3 -> null

После третьего:

previous -> 3 -> 2 -> 1 -> null
current -> null

Возвращаем узел со значением 3, потому что это новая голова.

Ключевой момент - сохранить next до изменения current.next. Если этого не сделать, мы потеряем доступ к оставшейся части списка.

Оценка сложности

Временная сложность

Мы посещаем каждый узел ровно один раз, поэтому временная сложность равна O(n).

Пространственная сложность

Мы используем только несколько указателей, поэтому дополнительная память равна O(1).

Код решения

Приведем код решения.

func reverseList(head *ListNode) *ListNode {
    var previous *ListNode
    current := head
    for current != nil {
        next := current.Next
        current.Next = previous
        previous = current
        current = next
    }
    return previous
}

Итоги

Разворот списка сводится к одному инварианту: previous всегда указывает на уже развернутую часть, а current - на еще не обработанную. Если сохранить следующий узел до изменения ссылки, весь алгоритм остается простым и линейным.

Войдите чтобы отмечать прогресс