В этой статье блога мы окунемся в увлекательный мир связанных списков и рассмотрим различные методы эффективного суммирования двух связанных списков. Независимо от того, являетесь ли вы новичком или опытным программистом, мы рассмотрим несколько подходов, используя разговорный язык, и предоставим примеры кода, которые помогут вам освоить это упражнение. Итак, давайте начнем и взломаем код суммирования двух связанных списков!

Метод 1: итеративный подход
Один из самых простых способов суммировать два связанных списка — использовать итеративный подход. Мы пройдемся по обоим спискам одновременно, суммируя соответствующие элементы и отслеживая любой перенос. Вот фрагмент кода, иллюстрирующий этот метод:

def sum_linked_lists(head1, head2):
    result_head = Node(0)  # Dummy head for the result
    current = result_head
    carry = 0
    while head1 or head2 or carry:
        sum_val = carry
        if head1:
            sum_val += head1.val
            head1 = head1.next
        if head2:
            sum_val += head2.val
            head2 = head2.next
        carry = sum_val // 10
        current.next = Node(sum_val % 10)
        current = current.next
    return result_head.next

Метод 2: рекурсивный подход
Еще один элегантный подход — использование рекурсии. Мы будем рекурсивно проходить по связанным спискам, суммируя соответствующие элементы и распространяя любой перенос. Вот пример фрагмента кода:

def sum_linked_lists(head1, head2, carry=0):
    if not head1 and not head2 and not carry:
        return None
    sum_val = carry
    if head1:
        sum_val += head1.val
        head1 = head1.next
    if head2:
        sum_val += head2.val
        head2 = head2.next
    node = Node(sum_val % 10)
    carry = sum_val // 10
    node.next = sum_linked_lists(head1, head2, carry)
    return node

Метод 3: обращение и суммирование
Если связанные списки расположены в обратном порядке (цифра единиц в начале), мы можем перевернуть их, суммировать, используя итеративный или рекурсивный подход, упомянутый выше, а затем обратить результат обратно. Такой подход упрощает логику обработки переноса. Вот фрагмент кода, демонстрирующий это:

def reverse_linked_list(head):
    prev = None
    current = head
    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    return prev
def sum_linked_lists_reverse(head1, head2):
    reversed_head1 = reverse_linked_list(head1)
    reversed_head2 = reverse_linked_list(head2)
    result = sum_linked_lists(reversed_head1, reversed_head2)
    result = reverse_linked_list(result)
    return result