Как добавить 2 односвязных списка вместе?

Question

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

Ex Функция: add_linked_list_integers (a, b) - где a и b являются односвязными спискамичьи узлы содержат одну цифру положительного целого числа.

Ex Проблема: 617 + 295 = 912 будет представлен в связанных списках как (7-> 1-> 6) + (5-> 9-> 2) = (2-> 1-> 9).

Мне предоставляется базовый класс ListNode и примеры функций для печати и создания связного списка целых чисел.

class ListNode:
    '''Simple node for singly-linked list with _value and _next fields'''
    def __init__(self, value, next=None):
        '''Create a new node, with _value field and optional _next node pointer'''
        self._value = value
        self._next = next

def print_helper(l):
    '''Prints the value of the integer represented by the linked-list l, without trailing carriage return'''
    if l:
        if (l._value < 0) or (l._value > 9):
            raise Exception('digit out of range')
        print_helper(l._next)
        print(l._value, end="")

def print_linked_list_integer(l):
    '''Prints the value of the integer represented by the linked-list l, with trailing carriage return'''
    print_helper(l)
    print()

def create_linked_list_integer(i):
    '''Returns the linked-list representation of the integer i, least-significant digit first'''
    result = ListNode(i % 10)
    if i >= 10:
        result._next = create_linked_list_integer(i // 10)
    return result

def add_linked_list_integers(a, b):
    '''Return the sum of two integers represented as linked lists

В настоящее время моя функция выглядит следующим образом:

def add_linked_list_integers(a, b):
    '''Return the sum of two integers represented as linked lists'''
    answer = ListNode()
    if a == None:
        return b
    elif b == None:
        return a
    carry = 0
    result = (a.data + b.data + carry)
    if result > 9:
        result = result - 10
        carry = 1
        answer.push(result)
    return answer

Answer 1

def add_linked_list_integers(a, b):
    '''Return the sum of two integers represented as linked lists'''
    pre_head = ListNode(-1)

    carry = 0
    head = pre_head
    while a is not None and b is not None:
        digit = (a._value + b._value + carry) % 10
        carry = (a._value + b._value + carry) // 10

        head._next = ListNode(digit)
        head = head._next
        a = a._next
        b = b._next

    while a is not None:
        digit = (a._value + carry) % 10
        carry = (a._value + carry) // 10
        head._next = ListNode(digit)
        head = head._next
        a = a._next

    while b is not None:
        digit = (b._value + carry) % 10
        carry = (b._value + carry) // 10
        head._next = ListNode(digit)
        head = head._next
        b = b._next            

    if carry != 0:
        head._next = ListNode(carry)

    return pre_head._next

Это то, что я бы сделал

Answer 2

Просто выполните эквивалент добавления базы-10. Это означает циклический переход по цифрам!

from itertools import zip_longest

def add_linked_list_integers(xs, ys):
    carry = 0
    result = []

    for x, y in zip_longest(xs, ys, fillvalue=0):
        s = x + y + carry
        carry = s // 10
        result.append(s % 10)

    if carry > 0:
        result.append(carry)

    return result

Пример выполнения:

>>> add_linked_list_integers([7, 1, 6], [5, 9, 2])
[2, 1, 9]

>>> to_list = lambda y: [int(x) for x in reversed(str(y))]
>>> to_int  = lambda xs: int(''.join(str(x) for x in xs)[::-1])

>>> a, b = 3192097619, 999999998472534892

>>> a + b
1000000001664632511

>>> to_int(add_linked_list_integers(to_list(a), to_list(b)))
1000000001664632511