В этом сообщении блога мы попрактикуемся в решении некоторых проблем алгоритмов. И сегодня наша задача с leetcode: Сложить два числа.
Определение проблемы:
Вам даны два непустых связанных списка, представляющих два неотрицательных целых числа. Цифры хранятся в обратном порядке, и каждый из их узлов содержит одну цифру. Сложите два числа и верните его в виде связанного списка.
Вы можете предположить, что эти два числа не содержат нуля в начале, кроме самого числа 0.
Связанный список
Сначала давайте разберемся, что такое связанные списки. Связанный список - это структура данных, в которой линейно хранится несколько значений. Каждое значение - это его узел / объект совы, который хранит значение и ссылается на следующий узел / объект в списке. Это выглядит так:
function ListNode(val) {
this.val = val;
this.next = null;
}
И вот как мы создаем связанный список:
// add a first node const head = new LinkedListNode(1); // add a second node head.next = new LinkedListNode(2); // add a third node head.next.next = new LinkedListNode(3);
Процесс мышления
У нас есть два перевернутых связанных списка, и нам нужно перебирать каждый из них одновременно и добавлять значения из обоих списков друг в друга. В результате нам нужно вернуть новый связанный список с суммой значений.
Нам нужно нести ценность. Потому что в каждом узле должно быть однозначное значение. Если вы сложите 5 + 5, результат будет 10, так что вы живете 0 в последнем узле и перемещаете 1 на следующий узел. И в следующем узле вы добавите к сумме 1.
В нашем решении мы будем использовать цикл while для перебора каждого узла в обоих связанных списках. Условие цикла while выглядит так:
while(l1 || l2 || sum > 0)
И внутри цикла мы назначим l1 и l2 заголовку связанного списка. Затем выполните сложение, добавьте сумму в новый связанный список и перейдите к следующему узлу. Если l1 или l2 не ложны, они продолжают цикл. Это будет работать, даже если у нас нет связанных списков одинакового размера.
Также в конце функции мы присвоим сумме значение переноса, и даже если у нас есть пустые l1 и l2, значение переноса будет добавлено в окончательный связанный список.
Решение
Вот как выглядит финальная функция:
Что leetcode думает о нашем решении?
Заключение
Эта проблема очень популярна на собеседованиях по кодированию. Если вы можете решить эту проблему, это показывает, что у вас есть понимание структур данных, выходящих за рамки встроенных структур данных, таких как массивы и объекты.
Продолжайте учиться, продолжайте расти!
Присоединяйтесь к LinkedIn!
