Задача: 445. Add Two Numbers II
Сложность: medium

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

Пример:

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

👨‍💻 Алгоритм:

1⃣Создайте два связанных списка r1 и r2, чтобы хранить перевернутые связанные списки l1 и l2 соответственно. Создайте два целых числа totalSum и carry для хранения суммы и переноса текущих цифр. Создайте новый ListNode, ans, который будет хранить сумму текущих цифр. Мы будем складывать два числа, используя перевернутый список, добавляя цифры по одной. Продолжаем, пока не пройдем все узлы в r1 и r2.

2⃣Если r1 не равен null, добавляем r1.val к totalSum. Если r2 не равен null, добавляем r2.val к totalSum. Устанавливаем ans.val = totalSum % 10. Сохраняем перенос как totalSum / 10. Создаем новый ListNode, newNode, который будет иметь значение как перенос. Устанавливаем next для newNode как ans. Обновляем ans = newNode, чтобы использовать ту же переменную ans для следующей итерации. Обновляем totalSum = carry.

3⃣Если carry == 0, это означает, что newNode, созданный в финальной итерации цикла while, имеет значение 0. Поскольку мы выполняем ans = newNode в конце каждой итерации цикла while, чтобы избежать возврата связанного списка с головой, равной 0 (начальный ноль), возвращаем следующий элемент, т.е. возвращаем ans.next. В противном случае, если перенос не равен 0, значение ans не равно нулю. Следовательно, просто возвращаем ans.

😎 Решение:

class ListNode {
    public $val = 0;
    public $next = null;
    function __construct($val = 0, $next = null) {
        $this->val = $val;
        $this->next = $next;
    }
}

class Solution {
    function reverseList($head) {
        $prev = null;
        $temp = null;
        while ($head != null) {
            $temp = $head->next;
            $head->next = $prev;
            $prev = $head;
            $head = $temp;
        }
        return $prev;
    }

    function addTwoNumbers($l1, $l2) {
        $r1 = $this->reverseList($l1);
        $r2 = $this->reverseList($l2);

        $totalSum = 0;
        $carry = 0;
        $ans = new ListNode(0);
        while ($r1 != null || $r2 != null) {
            if ($r1 != null) {
                $totalSum += $r1->val;
                $r1 = $r1->next;
            }
            if ($r2 != null) {
                $totalSum += $r2->val;
                $r2 = $r2->next;
            }

            $ans->val = $totalSum % 10;
            $carry = intdiv($totalSum, 10);
            $head = new ListNode($carry);
            $head->next = $ans;
            $ans = $head;
            $totalSum = $carry;
        }

        return $carry == 0 ? $ans->next : $ans;
    }
}

Ставь 👍 и забирай 📚 Базу знаний