1.题目

原题：

给定两个非空链表来表示两个非负整数。位数按照逆序方式存储，它们的每个节点只存储单个数字。将两数相加返回一个新的链表。假设除了数字 0 之外，这两个数字都不会以零开头。

例子：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)  实际是[2,4,3] [5,6,4]
输出：7 -> 0 -> 8   实际是[7,0,8]
原因：342 + 465 = 807

2.解析

这道题属于比较基础的算法题，没有涉及特别多复杂的逻辑。笔者选用python进行编程，这里需要解决的两个核心问题，第一个是python实现单链表，第二个是各位相加的逢十进一（进制问题）。

• python实现单链表：
  定义一个Node，Node包括两个属性，value和next，通过循环实现链表结构，对于链表的其他操作，如插入、删除等也是比较有意思的知识点，大家可以自行探索，本处不涉及。
• 各位相加的逢十进一
  由于非负整数是倒序排列，各个位都是一一对应的，不用考虑两个整数长度不一致的问题。进制控制可以增加一个flag，但凡涉及到进位将flag设置为1，参与下一次计算。

3.python代码

class Node:
    def __init__(self, value=None, next=None):
        self.value = value
        self.next = next


class Solution:
    def add_2_number(self, l1, l2):
        if l1 is None:
            return l2
        if l2 is None:
            return l1
        jinzhi = 0
        head = Node(0)
        l = head
        while l1 or l2 or jinzhi:#控制计算进行的条件
            sum, jinzhi = jinzhi, 0
            if l1:
                sum += l1.value
                l1 = l1.next
            if l2:
                sum += l2.value
                l2 = l2.next
            if sum > 9:
                jinzhi = 1
                sum -= 10
            head.next = Node(sum)
            head = head.next
        return l.next

#辅助函数，用于将list转为列表
def list_2_lianbiao(input):
    if not input:
        return None
    head = Node(input[0])
    input.pop(0)
    output = head
    while input:
        head.next = Node(input[0])
        head = head.next
        input.pop(0)
    return output


if __name__ == '__main__':
    l1 = list_2_lianbiao([1, 2, 3, 4])
    l2 = list_2_lianbiao([2, 9, 8, 7])
    newS = Solution()
    newl = newS.add_2_number(l1, l2)
    while newl:
        print(newl.value)
        newl = newl.next