如何将单个链表的递归元素转换为迭代解[重复]

Question

这个问题在这里已有答案：

• Way to go from recursion to iteration 19个答案

我们有两个单链表;因此，我们只能在单一方向上穿越结构。此外，我们只能访问链表的头部。算法的目标是对两个链表的数字求和，并用答案产生第三个。例如，链表[6,1,7] + [2,9,5]应该产生结果[9,1,2]，假设617 + 295 = 912。

为简单起见，我们将假设原始列表的长度相同。同样，我没有实现链表数据结构;相反，我正在使用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的伟大着作“Cracking the Coding Interview”中的原始问题。

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]