Давайте решим задачу LeetCode среднего уровня в LinkedList — «Добавить два числа».

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

Решение

Решение задачи довольно простое, и его легко понять, просто взглянув на приведенный ниже код.

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

Обратите внимание на несколько вещей, которые явно обрабатываются в приведенном выше коде.

  1. Цифра считается равной 0, если в связанном списке нет соответствующего узла.
  2. Переход к следующему узлу, только если он существует.
  3. После добавления всех узлов из обоих списков может остаться перенос — его нужно добавить в конец.

Временная сложность = O(n)
Пространственная сложность = O(n)

Обучение

Наша цель не должна состоять только в том, чтобы решить постановку задачи. Скорее мы должны определить, какие концепции мы изучили, чтобы мы могли применять их в будущем.

Обычно, если результатом является связанный список, ожидается, что будет возвращен головной узел связанного списка. И мы можем легко потерять голову во время итерации. Итак, лучше иметь фиктивный узел, всегда указывающий на голову, который мы можем вернуть в конце. Например, dummyHeadNode в приведенном выше решении.

Спасибо и увидимся в следующем посте. Приятного обучения!