445. Сложите два числа II

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

Вы можете предположить, что эти два числа не содержат начальных нулей, кроме самого числа 0.

Пример 1:

Input: l1 = [7,2,4,3], l2 = [5,6,4]
Output: [7,8,0,7]

Пример 2:

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [8,0,7]

Пример 3:

Input: l1 = [0], l2 = [0]
Output: [0]

Ограничения:

• Количество узлов в каждом связанном списке находится в диапазоне [1, 100].
• 0 <= Node.val <= 9
• Гарантируется, что список представляет собой число, не имеющее лидирующих нулей.

Дополнение. Не могли бы вы решить эту проблему, не меняя местами входные списки?

Интуиция:

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

Подход 1: (Обратный LL):

Код

C++

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = NULL;
        while(head) {
            ListNode* nxt = head->next;
            head->next = prev;
            prev = head;
            head = nxt;
        }
        return prev;
    }
    ListNode* Helper(ListNode* l1, ListNode* l2) {
        ListNode* dummyHead = new ListNode(0);
        ListNode* tail = dummyHead;
        int carry = 0;
        while (l1 != nullptr || l2 != nullptr || carry != 0) {
            int digit1 = (l1 != nullptr) ? l1->val : 0;
            int digit2 = (l2 != nullptr) ? l2->val : 0;
            int sum = digit1 + digit2 + carry;
            int digit = sum % 10;
            carry = sum / 10;
            ListNode* newNode = new ListNode(digit);
            tail->next = newNode;
            tail = tail->next;
            l1 = (l1 != nullptr) ? l1->next : nullptr;
            l2 = (l2 != nullptr) ? l2->next : nullptr;
        }
        ListNode* result = dummyHead->next;
        delete dummyHead;
        return result;
    }
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        l1 = reverseList(l1);
        l2 = reverseList(l2);
        ListNode* ans = Helper(l1, l2);
        return reverseList(ans);
    }
};