Задачник по алгоритмам

Программа курса:

Задача 3: Удаление элементов связанного списка

Напишите определение функции remove_elements(head, val), которая принимает два аргумента:

  • head — голова связанного списка (представленного в виде массива).
  • val — значение, которое нужно удалить из всех узлов списка.

Функция должна вернуть новую голову связанного списка, в котором все узлы с заданным значением val удалены. Если таких узлов нет, список остается без изменений.

Описание объекта ListNode:

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

ListNode — это объект, представляющий узел в односвязном списке. Каждый узел имеет два атрибута:

  1. val — значение, которое хранится в узле. Это может быть любое значение (например, целое число).
  2. next — указатель на следующий узел в списке. Если узел является последним, то этот атрибут равен None.

Пример структуры списка:

  • 1 -> 2 -> 6 -> 3 -> 4 -> 5 -> 6 -> None

Примеры:

Пример 1:

Ввод:

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

Объяснение:

  1. Начальный список:
    1 -> 2 -> 6 -> 3 -> 4 -> 5 -> 6 -> None
  2. Мы хотим удалить все узлы со значением 6.
  3. После первого удаления первого узла с 6:
    1 -> 2 -> 3 -> 4 -> 5 -> 6 -> None
  4. После второго удаления второго узла с 6:
    1 -> 2 -> 3 -> 4 -> 5 -> None

Выход:

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

Пример 2:

Ввод:

head = []
val = 1

Объяснение:

  1. Список пуст, так что никаких изменений не происходит.
  2. Возвращается пустой список.

Выход:

head = []

Пример 3:

Ввод:

head = [7, 7, 7, 7]
val = 7

Объяснение:

  1. Начальный список:
    7 -> 7 -> 7 -> 7 -> None
  2. Все узлы содержат значение 7, поэтому все узлы будут удалены.
  3. Возвращается пустой список.

Выход:

head = []

0
Вы должны Войти или Зарегистрироваться чтобы оставлять комментарии