Question 2
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Example
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
题目分析
输入：本题的输入是两个自然数，每个数都逆序放在链表里，比如例子中的 (2 -> 4 -> 3)实际上是342。并且默认除了0以外，自然数的不会以0作为开头，也就是说342不会以 (2 -> 4 -> 3 - > 0)的形式存在（即0342）。
处理：函数作用是将两个链表中的自然数相加，同样除了0以外的数不以0开头，比如例子中342+465=807。
输出：将结果以链表形式输出，即把结果807用链表 (7 -> 0 -> 8)输出。
检验设置
TDD(Test-driven development) analysis:
1. 最简单的情形是两个数位数相同且加和不进位：
l1 = (2 -> 4 -> 3), l2 = (3 -> 2 -> 5)
>>> (5 -> 6 -> 8)
2. 同样加和不进位的情形下，使两个数位数不同：
l1 = (2 -> 4 -> 3), l2 = (2 -> 5)
>>> (4 -> 9 -> 3)
3. 位数相/不同的两个数加和进位，但保持结果的链表长度等于输入两个链表的最大长度：
l1 = (2 -> 4 -> 3), l2 = (3 -> 7 -> 5)
>>> (5 -> 1 -> 9)
4. 位数相/不同的两个数加和进位，且结果的链表长度大于输入两个链表的最大长度：
l1 = (2 -> 4 -> 3), l2 = (3 -> 7 -> 6)
>>> (5 - > 1 -> 0 -> 1)
5. 特殊情况，两个数都是0：
l1 = (0), l2 = (0)
>>> (0)
链表的结构要事先定义好，这里与题目给出的class一致，链表当中的值用val表示，连接用next表示，如下
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
为了方便检验，还需要写两个函数分别实现创建链表和显示链表的功能。
#根据输入的列表创建链表，列表与链表的顺序一致
#l = [2, 4, 3]（代表自然数342）
#>>> (2 - > 4 - > 3)
def createListNode(l):
head = temp = ListNode(0)
#先设置一个head，像基因编码一样找一个生成器
for i in l:
temp.next = ListNode(i)
#将输入list中的每个元素变成一个链表结构
temp = temp.next
return head.next
#返回需要的链表，扔掉编码开始的head
#显示链表
#l = (2 - > 4 - > 3)
#>>> 243
def printListNode(ln):
while ln:
print(ln.val, end = '')
#按照链表顺序输出value，同时不换行
ln = ln.next
print('')
#换行，使得后续输出的结果在新一行出现，容易辨认
1.直接解法（Python3）:
既然是在自然数加法上复合了链表，直接的解法是单独处理链表与加和：先把输入的链表转换为自然数，再把加和后的结果转换为链表。
def addTwoNumbers(l1, l2):
def lnToInt(ln):
#将链表（缩写为名称的ln，listnode）转化为整型数（缩写为名称的int）
num = count = 0
#num代表转化后的整型数，count代表数位
while ln:
num += ln.val * pow(10, count)
#把链表每个数字放到整型数对应的位数上，所以乘以了10的count次方
count += 1
ln = ln.next
return num
def intToLn(n):
#将整型数转换为链表
head = temp = ListNode(0)
#先设置一个head，像基因编码一样找一个生成器
if n == 0:
return head
#如果整型数为0，直接返回链表(0)，这也是head设置为ListNode(0)的好处
while n:
temp.next = ListNode(n % 10)
#找到余数，也就是链表对应的1位数元素
temp = temp.next
n = n // 10
#获得剩下未转换为链表的整型数
return head.next
sum = lnToInt(l1) + lnToInt(l2)
return intToLn(sum)
时间复杂度O(n)，空间复杂度O(n)，链表与加和分开处理的思考难度低，但是效率被浪费在链表和自然数的相互转化中，可以继续优化，方向是赋予链表加和能力。
2.链表的加法运算：
实现链表加法的核心有两个：进位问题和链表长度变化问题。这两个问题都是由链表表示自然数的规定引发的，规定中要求每一个链表元素都只能是1位数，如果加和出现两位数是在链表中间，就是进位问题，在链表末端就是长度变化问题。解决方案是用一个变量来记录进位的数字，比如用carry来记录，链表的元素取加和后结果的个位数，比如，5+7=12，这时链表的元素取个位数2，carry=1，当下一位进行计算的时候把carry的值加入。
def addTwoNumbersNode(l1, l2):
head = temp = ListNode(0)
#先设置一个head，像基因编码一样找一个生成器
carry = 0
#用来存放加和是两位数时的十位数
while l1 or l2 or carry:
#只有当l1和l2是null，且carry是0的时候才停止生成链表
value1 = l1.val if l1 else 0
value2 = l2.val if l2 else 0
sum = value1 + value2 + carry
temp.next = ListNode(sum % 10)
#链表的元素是加和值的个位数
carry = sum // 10
#carry的值是加和值的十位数
temp = temp.next
l1 = l1.next if l1 else None
l2 = l2.next if l2 else None
return head.next
时间复杂度O(n)，空间复杂度O(n)，实现了链表和加法的功能组合。
