Сложение двух связных списков

Решение: Сложение двух связных списков

Эта задача требует работы со связными списками. Ключевой момент — цифры хранятся в обратном порядке, что упрощает сложение (начинаем с младших разрядов).

Алгоритм решения

1. Создаём новый связный список для результата
2. Инициализируем переменную переноса (carry) = 0
3. Проходим по обоим спискам одновременно:
   • Берём значение из первого списка (или 0, если список закончился)
   • Берём значение из второго списка (или 0, если список закончился)
   • Складываем оба значения + carry из предыдущей итерации
   • Новая цифра = сумма % 10
   • Новый carry = сумма // 10
   • Добавляем новый узел в результирующий список
4. Если после окончания списков остался carry — добавляем его в результат
5. Возвращаем результирующий список

Структура узла списка

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

Реализация решения

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def addTwoNumbers(l1: ListNode, l2: ListNode) -> ListNode:
    # Создаём фиктивный узел для упрощения логики
    dummy_head = ListNode(0)
    current = dummy_head
    carry = 0
    
    # Проходим по обоим спискам
    while l1 or l2 or carry:
        # Получаем значения из узлов (если они существуют)
        val1 = l1.val if l1 else 0
        val2 = l2.val if l2 else 0
        
        # Суммируем значения и перенос
        total = val1 + val2 + carry
        
        # Вычисляем новую цифру и перенос
        carry = total // 10
        digit = total % 10
        
        # Создаём новый узел и добавляем в результат
        current.next = ListNode(digit)
        current = current.next
        
        # Переходим к следующим узлам (если они существуют)
        l1 = l1.next if l1 else None
        l2 = l2.next if l2 else None
    
    return dummy_head.next

Пошаговый разбор примера

Вход: 2->4->3 (342), 5->6->4 (465)

Итерация 1:

• val1 = 2, val2 = 5, carry = 0
• total = 2 + 5 + 0 = 7
• digit = 7, carry = 0
• result: 7

Итерация 2:

• val1 = 4, val2 = 6, carry = 0
• total = 4 + 6 + 0 = 10
• digit = 0, carry = 1
• result: 7->0

Итерация 3:

• val1 = 3, val2 = 4, carry = 1
• total = 3 + 4 + 1 = 8
• digit = 8, carry = 0
• result: 7->0->8

Итерация 4:

• l1 = None, l2 = None, carry = 0 → выход из цикла

Выход: 7->0->8 (807) ✓

Вспомогательные функции для тестирования

def create_list(digits: list) -> ListNode:
    """Создаёт связный список из массива цифр"""
    if not digits:
        return None
    head = ListNode(digits[0])
    current = head
    for digit in digits[1:]:
        current.next = ListNode(digit)
        current = current.next
    return head

def list_to_array(node: ListNode) -> list:
    """Преобразует связный список в массив"""
    result = []
    while node:
        result.append(node.val)
        node = node.next
    return result

# Тесты
l1 = create_list([2, 4, 3])
l2 = create_list([5, 6, 4])
result = addTwoNumbers(l1, l2)
print(list_to_array(result))  # [7, 0, 8]

Сложность

• Временная сложность: O(max(m, n)), где m и n — длины списков
• Пространственная сложность: O(max(m, n)) для создания нового списка

Особенности решения

• Фиктивный узел упрощает логику — не нужно проверять, существует ли head результата
• Обработка переноса правильно работает для всех случаев, включая последний перенос
• Универсальность — решение работает для списков разной длины

Решение имеет оптимальную сложность и корректно обрабатывает все граничные случаи.