Сложить два числа, которые представлены списком



Даны 2 непустых списка, в которых закодированы, соответственно, два неотрицательных чила. Цифры каждого числа хранятся в обратном порядке. В каждоя ячейке списка находится одна цифра. Сложить эти два числа и вернуть их в виде списка.

Можно предположить, что заданные числа не начинаются с нуля, за исключением если они и есть 0.

Пример:
Дано: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Резальтат: 7 -> 0 -> 8
Пояснение: 342 + 465 = 807.
Идея решения.
В начале каждого списка установим указатель, они будут смещаться одновременно складывая числа ячеек: a+b по правилам сложения в столбик.


Имплементация.
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummyHead = new ListNode(0); // запоминаем начало результирующего списка
    ListNode p = l1, q = l2, curr = dummyHead;
    int carry = 0;
    while (p != null || q != null) {
        int x = (p != null) ? p.val : 0;
        int y = (q != null) ? q.val : 0;
        int sum = carry + x + y;
        carry = sum / 10;
        curr.next = new ListNode(sum % 10);
        curr = curr.next;
        if (p != null) p = p.next;
        if (q != null) q = q.next;
    }
    if (carry > 0) {
        curr.next = new ListNode(carry);
    }
    return dummyHead.next;
}

Комментарии

Популярные сообщения из этого блога

Разбиение числа на сумму с максимальным произведнием слагаемых

Число подмассивов, в которых сумма элементов равна k