Простой алгоритм с анализом временной и пространственной сложности

Связный список — это структура данных, состоящая из узлов, где каждый узел содержит значение и указатель на следующий узел в списке. Обращение связанного списка включает изменение направления указателей, поэтому первый узел становится последним, второй узел становится предпоследним и так далее. В этой статье мы рассмотрим простой алгоритм обращения связанного списка и проанализируем его временную и пространственную сложность.

Алгоритм

Алгоритм обращения связанного списка может быть реализован итеративно или рекурсивно. Здесь мы сосредоточимся на итеративном подходе, поскольку он является более простым и эффективным с точки зрения пространственной сложности.

Рассмотрим связанный список со следующей структурой:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

Чтобы перевернуть связанный список, мы будем поддерживать три указателя: `current`, `previous` и `далее`. Мы будем перебирать связанный список, обновляя указатели следующим образом:

  1. Инициализируйте `current` как заголовок связанного списка, а `previous` и `next` как `None`.
  2. Перемещайтесь по списку, используя цикл, пока `current` не станет `None`.
  3. В каждой итерации сохраняйте следующий узел `current` в указателе `next`.
  4. Установите указатель `next` для `current` на `previous`.
  5. Переместить `предыдущее` в `текущее`.
  6. Переместить `текущий` в `следующий`.
  7. Повторяйте шаги 3–6, пока не будет достигнут конец связанного списка.
  8. Наконец, обновите заголовок обратно связанного списка как `previous`.

Выполнение:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


def reverseLinkedList(head):
    prev = None
    current = head

    while current is not None:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node

    return prev

Анализ временной сложности

Временная сложность итеративного подхода к обращению связанного списка составляет O(N), где N — количество узлов в списке. Это связано с тем, что мы проходим весь список один раз, выполняя операции с постоянным временем для каждого узла.

Анализ космической сложности

Объемная сложность итеративного подхода составляет O(1), так как мы используем фиксированный объем дополнительного пространства только для трех указателей (`current`, `previous ` и `далее`). Независимо от размера связанного списка объем требуемого дополнительного пространства остается постоянным.

Заключение

Реверсирование связанного списка — фундаментальная операция, которую можно эффективно выполнить с помощью итеративного подхода. Следуя простому алгоритму, описанному в этой статье, вы можете обратить связанный список в линейную временную сложность (O(N)) и постоянную пространственную сложность (O(1)). Понимание временной и пространственной сложности алгоритмов имеет решающее значение для разработки эффективных решений и оптимизации производительности кода в различных приложениях.

Удачного программирования!