2. Add Two Numbers

Задача

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

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

Примеры

Пример 1

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

Пояснение

342 + 465 = 807.

Пример 2

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

Пример 3

Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]

Решение

Тестирование

// Определение узла односвязного списка
function ListNode(val, next) {
    this.val = (val === undefined ? 0 : val);
    this.next = (next === undefined ? null : next);
}
 
// Вспомогательная функция: массив -> связный список
function createLinkedList(arr) {
    let dummy = new ListNode(0);
    let current = dummy;
    for (let num of arr) {
        current.next = new ListNode(num);
        current = current.next;
    }
    return dummy.next;
}
 
// Вспомогательная функция: связный список -> массив (для проверки ответа)
function linkedListToArray(head) {
    let arr = [];
    while (head) {
        arr.push(head.val);
        head = head.next;
    }
    return arr;
}
 
// --- Тестовые данные ---
 
// Example 1: 342 + 465 = 807
const l1_1 = createLinkedList([2, 4, 3]);
const l2_1 = createLinkedList([5, 6, 4]);
 
// Example 2: 0 + 0 = 0
const l1_2 = createLinkedList([0]);
const l2_2 = createLinkedList([0]);
 
// Example 3: 9999999 + 9999 = 10009998
const l1_3 = createLinkedList([9, 9, 9, 9, 9, 9, 9]);
const l2_3 = createLinkedList([9, 9, 9, 9]);
 
// --- Место для вызова твоей функции addTwoNumbers ---
// const resultHead = addTwoNumbers(l1_1, l2_1);
// console.log(linkedListToArray(resultHead)); // Должно вывести [7, 0, 8]

Решение 1 (Loop)

/**
 * Временная сложность: O(max(N, M))
 * Пространственная сложность: O(max(N, M))
 */
var addTwoNumbers = function(l1, l2) {
    const dummy = new ListNode(0);
    let current = dummy;
    let pass = 0;
 
    // Цикл продолжается, пока есть узлы в l1 ИЛИ в l2 ИЛИ остался перенос (pass)
    while (l1 || l2 || pass) {
        const sum = (l1?.val || 0) + (l2?.val || 0) + pass;
 
        pass = sum >= 10 ? 1 : 0;
 
        current.next = new ListNode(sum % 10);
        current = current.next;
 
        l1 = l1?.next;
        l2 = l2?.next;
    }
 
    return dummy.next;
};

Решение 2 (Recursion)

/**
 * Можно написать ту же логику, но через рекурсию. Это выглядит элегантно, но тратит лишнюю память на стек вызовов (O(N) дополнительной памяти).
 * 
 * Временная сложность: O(max(N, M))
 * Пространственная сложность: O(max(N, M)) (стек рекурсии + результат)
 */
var addTwoNumbers = function(l1, l2, carry = 0) {
    if (!l1 && !l2 && !carry) return null;
 
    const sum = (l1?.val || 0) + (l2?.val || 0) + carry;
    const nextCarry = Math.floor(sum / 10);
 
    const node = new ListNode(sum % 10);
 
    // Рекурсивно вызываем для следующих узлов
    node.next = addTwoNumbers(l1?.next, l2?.next, nextCarry);
 
    return node;
};