Пример решения задачи #2 на Python LeetCode — Сложить два числа

Вариант решения задачи на языке программирования Python с LeetCode.
Категория: Алгоритмы.
Название задачи: Сложить два числа (Add Two Numbers).
Сложность: Средняя.
Статус решения: "Решено".

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

Решение:

Python

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: Optional[ListNode]
        :type l2: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        # Создаем фиктивного узел, который будет началом результирующего списка
        dummy_head = ListNode(0)
        # Устанавливаем текущий узел равным временному узлу
        current = dummy_head
        # Устанавливаем перенос равным 0
        carry = 0

        # Пока l1 или l2 не пустые или есть перенос
        while l1 is not None or l2 is not None or carry != 0:
            # Если l1 не пуст, берем его значение, иначе 0
            val1 = l1.val if l1 is not None else 0
            # Если l2 не пуст, берем его значение, иначе 0
            val2 = l2.val if l2 is not None else 0
            # Считаем сумму значений и переноса
            sum_ = val1 + val2 + carry
            # Устанавливаем перенос равным 1, если сумма больше или равна 10, иначе 0
            carry = 1 if sum_ >= 10 else 0
            # Создаем новый узел с остатком от деления суммы на 10
            new_node = ListNode(sum_ % 10)
            # Добавляем новый узел в конец результирующего списка
            current.next = new_node
            # Переходим к следующему узлу в результирующем списке
            current = current.next
            # Если l1 не пуст, переходим к следующему узлу в l1
            if l1 is not None:
                l1 = l1.next
            # Если l2 не пуст, переходим к следующему узлу в l2
            if l2 is not None:
                l2 = l2.next

        # Возвращаем следующий узел после фиктивного узла, который является началом результирующего списка
        return dummy_head.next

Объяснение кода

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

Ключевые моменты:
Фиктивный узел: упрощает обработку первого узла.
Перенос: обеспечивает корректное сложение многозначных чисел.
Оператор % 10: используется для получения последней цифры числа.
Возврат dummy_head.next: исключает фиктивный узел из результата.

Источник решения: hdhai.com