Вам даны два непустых связанных списка, представляющих два неотрицательных целых числа. Цифры хранятся в обратном порядке , и каждый из их узлов содержит одну цифру. Добавьте два числа и верните сумму в виде связанного списка.
Вы можете предположить, что эти два числа не содержат начальных нулей, кроме самого числа 0.
Ограничения:
Количество узлов в каждом связанном списке находится в диапазоне[1, 100].0 <= Node.val <= 9
Гарантируется, что список представляет собой число, не имеющее лидирующих нулей.
Задача заключается в сложении двух чисел, представленных в виде связанных списков, где каждый узел хранит одну цифру числа. Сначала нужно пройти по обоим спискам, сложить соответствующие цифры чисел, начиная с младших разрядов, и сохранить результат в новый связанный список. Если сумма цифр превышает 9, то нужно запомнить единицу переноса и добавить ее к следующей сумме. Если какой-то список закончился раньше другого, то нужно просто продолжить сложение, используя нули вместо отсутствующих цифр.
Таким образом, алгоритм можно описать следующим образом:
- Создать новый связанный список, который будет содержать сумму двух чисел.
- Инициализировать два указателя на начало связанных списков.
- Инициализировать переменную для хранения единицы переноса.
- Пока оба указателя не достигнут конца связанных списков:
- Сложить две цифры из текущих узлов связанных списков и прибавить единицу переноса.
- Если сумма больше 9, то запомнить единицу переноса для следующей итерации.
- Создать новый узел в связанном списке с остатком от деления суммы на 10 (т.е. без учета единицы переноса).
- Перейти к следующим узлам обоих связанных списков.
- Если один из указателей дошел до конца связанного списка, а другой еще не дошел, то продолжить сложение с использованием нулей вместо отсутствующих цифр.
- Если после прохода по всем узлам осталась единица переноса, то добавить новый узел в конец связанного списка.
Временная сложность алгоритма составляет O(max(m, n)), где m и n — длины связанных списков, а пространственная сложность — O(max(m, n)+1), т.к. может потребоваться дополнительный узел для единицы переноса.
Решение Add Two Numbers LeetCode пример кода на Python
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
# создание фиктивной (dummy) ноды для возврата
dummy = ListNode()
# установка указателя текущей (curr) ноды на dummy
curr = dummy
# инициализация переменной carry для хранения "переноса" в следующий разряд
carry = 0
# цикл, который будет выполняться до тех пор, пока l1 или l2 содержат ноды или есть остаток от прошлого разряда (carry)
while l1 or l2 or carry:
# инициализация переменной sum как текущей суммы
sum = carry
# если l1 не равно None, то добавляем его значение в sum и перемещаемся на следующий узел
if l1:
sum += l1.val
l1 = l1.next
# если l2 не равно None, то добавляем его значение в sum и перемещаемся на следующий узел
if l2:
sum += l2.val
l2 = l2.next
# вычисляем carry для следующей итерации
carry = sum // 10
# создание новой ноды с результатом текущей суммы в текущем разряде
curr.next = ListNode(sum % 10)
# перемещаем указатель на следующую ноду
curr = curr.next
# возврат ноды, следующей за фиктивной нодой (dummy)
return dummy.next
class ListNode:
def __init__(self, val=0, next=None):
# инициализация значения текущей ноды (val) и указателя на следующую ноду (next)
self.val = val
self.next = next
Решение Add Two Numbers LeetCode пример кода на Java
public class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
// создание фиктивной (dummy) ноды для возврата
ListNode dummy = new ListNode(0, null);
// установка указателя текущей (curr) ноды на dummy
ListNode curr = dummy;
// инициализация переменной carry для хранения "переноса" в следующий разряд
int carry = 0;
// цикл, который будет выполняться до тех пор, пока l1 или l2 содержат ноды или есть остаток от прошлого разряда (carry)
while (l1 != null || l2 != null || carry != 0) {
// инициализация переменной sum как текущей суммы
int sum = carry;
// если l1 не равно null, то добавляем его значение в sum и перемещаемся на следующий узел
if (l1 != null) {
sum += l1.val;
l1 = l1.next;
}
// если l2 не равно null, то добавляем его значение в sum и перемещаемся на следующий узел
if (l2 != null) {
sum += l2.val;
l2 = l2.next;
}
// вычисляем carry для следующей итерации
carry = sum / 10;
// создание новой ноды с результатом текущей суммы в текущем разряде
curr.next = new ListNode(sum % 10, null);
// перемещаем указатель на следующую ноду
curr = curr.next;
}
// возврат ноды, следующей за фиктивной нодой (dummy)
return dummy.next;
}
} Решение Add Two Numbers LeetCode пример кода на C++
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
// создание фиктивной (dummy) ноды для возврата
ListNode *dummy = new ListNode(0, nullptr);
// установка указателя текущей (curr) ноды на dummy
ListNode *curr = dummy;
// инициализация переменной carry для хранения "переноса" в следующий разряд
int carry = 0;
// цикл, который будет выполняться до тех пор, пока l1 или l2 содержат ноды или есть остаток от прошлого разряда (carry)
while (l1 || l2 || carry) {
// инициализация переменной sum как текущей суммы
int sum = carry;
// если l1 не равно nullptr, то добавляем его значение в sum и перемещаемся на следующий узел
if (l1) {
sum += l1->val;
l1 = l1->next;
}
// если l2 не равно nullptr, то добавляем его значение в sum и перемещаемся на следующий узел
if (l2) {
sum += l2->val;
l2 = l2->next;
}
// вычисляем carry для следующей итерации
carry = sum / 10;
// создание новой ноды с результатом текущей суммы в текущем разряде
curr->next = new ListNode(sum % 10, nullptr);
// перемещаем указатель на следующую ноду
curr = curr->next;
}
// возврат ноды, следующей за фиктивной нодой (dummy)
return dummy->next;
}
}; Решение Add Two Numbers LeetCode пример кода на JavaScript
// объявляем функцию addTwoNumbers с двумя аргументами l1 и l2
var addTwoNumbers = function(l1, l2) {
// создаем новый узел и присваиваем его переменной dummy
let dummy = new ListNode();
// присваиваем переменной curr значение dummy
let curr = dummy;
// объявляем переменную carry и присваиваем ей значение 0
let carry = 0;
// запускаем цикл, который работает, пока l1, l2 или carry не станут равными null или 0 соответственно
while (l1 || l2 || carry) {
// объявляем переменную sum и присваиваем ей значение carry
let sum = carry;
// если l1 не равно null
if (l1) {
// добавляем значение l1.val к переменной sum
sum += l1.val;
// присваиваем l1 следующий узел
l1 = l1.next;
}
// если l2 не равно null
if (l2) {
// добавляем значение l2.val к переменной sum
sum += l2.val;
// присваиваем l2 следующий узел
l2 = l2.next;
}
// вычисляем остаток от деления суммы на 10 и присваиваем его переменной curr.next
curr.next = new ListNode(sum % 10);
// переназначаем curr на curr.next
curr = curr.next;
// вычисляем целое от деления суммы на 10 и присваиваем его переменной carry
carry = Math.floor(sum / 10);
}
// возвращаем следующий узел после dummy
return dummy.next;
};
Решение Add Two Numbers LeetCode пример кода на C#
public class Solution {
// объявляем метод AddTwoNumbers, который принимает два аргумента типа ListNode и возвращает ListNode
public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {
// создаем новый узел и присваиваем его переменной dummy
ListNode dummy = new ListNode();
// присваиваем переменной curr значение dummy
ListNode curr = dummy;
// объявляем переменную carry и присваиваем ей значение 0
int carry = 0;
// запускаем цикл, который работает, пока l1, l2 или carry не станут равными null или 0 соответственно
while (l1 != null || l2 != null || carry != 0) {
// объявляем переменную sum и присваиваем ей значение carry
int sum = carry;
// если l1 не равно null
if (l1 != null) {
// добавляем значение l1.val к переменной sum
sum += l1.val;
// присваиваем l1 следующий узел
l1 = l1.next;
}
// если l2 не равно null
if (l2 != null) {
// добавляем значение l2.val к переменной sum
sum += l2.val;
// присваиваем l2 следующий узел
l2 = l2.next;
}
// вычисляем целое от деления суммы на 10 и присваиваем его переменной carry
carry = sum / 10;
// вычисляем остаток от деления суммы на 10 и создаем новый узел с этим значением и присваиваем его переменной curr.next
curr.next = new ListNode(sum % 10);
// переназначаем curr на curr.next
curr = curr.next;
}
// возвращаем следующий узел после dummy
return dummy.next;
}
}
Если у вас не отображается решение последних задач, значит у вас включен блокировщик рекламы который вырезает эти ответы