Связный список для задач LeetCode (Easy)

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

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

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

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

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

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

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

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

Я хочу помочь желающим понять, как решать задачи на связный список. Ведь понимание — это лишь 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, что сильно мотивирует оптимизировать код!
  До встречи!