python - 如何将单链表递归元素和转换为迭代解决方案-6ren

python - 如何将单链表递归元素和转换为迭代解决方案

转载作者：塔克拉玛干更新时间：2023-11-03 06:37:13

<分区>

我们有两个单链表；因此，我们只能在一个方向上遍历结构。此外，我们只能访问链表的头部。该算法的目标是将两个链表的数字相加并产生第三个链表的答案。例如，鉴于 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