О чем эта статья?

Эта статья продолжает серию материалов про связный список для непрограммистов. В прошлой статье мы разобрали создание связного списка и методы итерации по нему. Теперь углубимся в практические аспекты работы с односвязными списками:

  • Как дойти до конца списка.

  • Как создавать новый связный список с использованием класса.

  • Как добавлять элементы в связный список в цикле, не создавая каждый узел отдельно.

  • Как работать с головой списка.

  • Как не выйти за границы списка при итерации.

Цель этой статьи

Я хочу помочь желающим понять, как решать задачи на связный список. Ведь понимание — это лишь 30% усилий, а остальные 70% усилий это практика.

Разбор задачи

Мы рассмотрим задачу 206. Reverse Linked List — переворот односвязного списка ( https://leetcode.com/problems/reverse-linked-list/description/ )

Условие

Дана голова односвязного списка. Переверните его и верните новый перевернутый список.

Вспомним как устроен связный список в python

Он всегда создаётся с помощью класса

В этой задаче этот класс выглядит вот так```

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

Когда мы работаем со связными списками, нам всегда на вход дают голову (head) списка, так как его структура - это цепочка, в которой каждый узел списка содержит ссылку на следующий элемент.

Пример

Вход:

1 → 2 → 3 → 4 → 5

Выход:

5 → 4 → 3 → 2 → 1

То есть, мы должны сохранить все узлы, поменять связи между ними и вернуть новую голову списка.

💡 Если вы хотите отслеживать каждый шаг вывода своего кода, то создайте этот список у себя, я любезно подготовила его 

class ListNode:
    def init(self, val=0, next=None):
        self.val = val
        self.next = next

node5 = ListNode(5, None) 

node4 = ListNode(4, node5) 

node3 = ListNode(3, node4) 

node2 = ListNode(2, node3) 

node1 = ListNode(1, node2)

Логика решения (псевдокод)

Решать задачу можно разными способами:

  • Добавить элементы в массив, затем собрать новый список.

  • Использовать рекурсию.

  • Решить итеративно в цикле while (наш метод) — оптимальнее по памяти и логичнее.

Что нужно сделать:

  1. Получить первый узел.

  2. Сохранить ссылку на следующий узел.

  3. Создать новый список, заполняя его значениями из исходного списка.

  4. Следить, чтобы не выйти за границы списка.

Ключевая идея:

  • Мы точно знаем, что первый узел исходного списка должен стать последним в новом списке.

  • А новые объекты создаются с конца, значит, нам удобно заполнять новый список прямо во время итерации!

Когда дошли до конца исходного списка, возвращаем голову нового списка.

Псевдокод для итеративного решения

def reverse_list(head):
    Step 1: Проверяем corner case
    Если head равно None или head.next равно None:
        Вернуть head (список уже пуст или состоит из одного элемента)

    Step 2: Инициализируем перевернутый список
    Создать новый узел my_list, содержащий значение из head, с указателем на None

    Step 3: Итерируемся по оставшейся части списка
    Пока head содержит следующий узел:
        Перемещаем head на следующий узел (head = head.next)

        NB! Нам нужно сохранить ссылку на текущий my_list перед обновлением
        next_node = my_list

        Создаем новый узел, содержащий значение из head, с указателем на next_node
        my_list теперь указывает на новый узел

    Вернуть my_list (новая голова развернутого списка)

Что здесь происходит?

  • Мы уже забрали первый узел из исходного списка и добавили его в новый.

  • Он нам больше не нужен, поэтому перекидываем голову на следующий узел (head = head.next).

  • Теперь head указывает на узел 2, а узел 1 уже находится в новом списке.

  • Чтобы сохранить связь и добавлять узлы в next, нам нужно запоминать предыдущий узел.

  • Поэтому перед каждой итерацией мы сохраняем текущий new_head в prev_node.

  • Далее создаём новый узел и указываем его next на prev_node.

  • Этот процесс повторяется до конца списка.

Таким образом, в каждом шаге:

  • Смещаем указатель head.

  • Сохраняем предыдущий узел.

  • Создаём новый узел и связываем его с предыдущим.

  • Повторяем процесс, пока не дойдём до конца.

    Финальная версия кода

    ```

    def reverseList(head):
    # Step 1: Проверяем corner case
    if not head or not head.next:
        return head

    # Step 2: Создаем первый узел нового списка
    my_list = ListNode(head.val, None)

    # Step 3: Итерируемся по оставшимся узлам
    while head.next is not None:
        head = head.next  # Переходим к следующему узлу
        
        next_node = my_list  # Сохраняем ссылку на текущую голову нового списка
        
        my_list = ListNode(head.val, next_node)  # Создаем новый узел и обновляем my_list

    return my_list  # Возвращаем голову развернутого списка

    ```

    Заключение

    В этой статье мы разобрали:

    ✅ Как работать с головой списка.

    ✅ Как перебирать узлы связного списка не выходя за границы списка.

    ✅ Как создавать новый связный список на основе существующего

    Если разобраться с односторонним списком, то двусвязный список не будет вызывать сложностей

    🔹 Если хочется решить по-другому, то вот идеи:

    • Как можно решить задачу рекурсивно? 🔄

    • Решить с использованием массива для временного хранения узлов 🗂️

    📊 И вы сможете сравнить пространственную и вычислительную сложность в инфографике на LeetCode, что сильно мотивирует оптимизировать код!
    До встречи!