如何将元素的单链表递归和转换为迭代解

Question

我们有两个单链表；因此，我们只能在一个方向上遍历结构。此外，我们只能访问链表的头部。该算法的目标是将两个链表的数字求和，并产生第三个链表和答案。例如，给定617 + 295 = 912，链表6，1，7+ 2，9，5应该产生结果9，1，2。

为了简单起见，我们将假定原始列表的长度相同。同样，我没有实现链表数据结构；相反，我使用的是Python的内置列表，但将它们视为链表。

我想出的解决方案如下(Python代码)

def sum_lists(l1, l2):
    lista = []
    carry = sum_forward(l1, l2, 0, lista)
    if carry > 0:
        lista.insert(0, carry) 
    return lista

def sum_forward(l1, l2, index, lista):
    if index == (len(l1)):        
        return 0
    total = l1[index] + l2[index] + sum_forward(l1, l2, index + 1, lista) #here
    #we have the iterative call.
    carry = total // 10
    value = total % 10    
    lista.insert(0, value) #This way we create a new head for the "surrogate     
    #linked-list" and append to it the resto of the values
    return carry

虽然这个解决方案工作得很好，但我听说任何递归解决方案都可以变成迭代解决方案。我已经尝试了几天，但我无法将其更改为迭代解决方案。

我知道这可以用很多方法来解决；然而，这真的可以转变为迭代解决方案吗？

谢谢你们！

我在Gayle Laakmann Mcdowell的伟大著作“破解编码面试”中发现了最初的问题，它的主题是链表。

Answer 1

这里有一个迭代的解决方案：

l1 = [6,1,7]
l2 = [2,9,5]

def iterative_sum(l1, l2):
    maxlength = max(len(l1), len(l2))
    lsum = []
    sup = 0
    for i in range(maxlength):
        if l1 and l2:
            sup, num = divmod(l1.pop() + l2.pop() + sup, 10)
        elif l1 or l2:
            lleft = l1 or l2 # this assigns lleft to one of l1, l2 that still had element
            sup, num = divmod(lleft.pop() + sup, 10)
        lsum.append(num)
    return lsum[::-1]

iterative_sum(l1, l2)
# [9, 1, 2]