这是崔斯特的第十篇原创文章
1、题目
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.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
2、思路
其实我并看不懂题目说得啥意思，如果说243+564，结果是807才是，但是很明显题目不会这么简单。怎么办？
好像只能去看看别人的理解了，发现：
1.因为存储是反过来的，即数字342存成2->4->3，所以要注意进位是向后的；
2.链表l1或l2为空时，直接返回，这是边界条件，省掉多余的操作；
3.链表l1和l2长度可能不同，因此要注意处理某个链表剩余的高位；
4.2个数相加，可能会产生最高位的进位，因此要注意在完成以上1－3的操作后，判断进位是否为0，不为0则需要增加结点存储最高位的进位。
给个链接http://blog.csdn.net/zhouworld16/article/details/14045855
原来是倒着相加，342+465=807，结果倒序，正好是708，题目应该是这样理解的吧，哈哈。
思路
本题的思路很简单，按照小学数学中学习的加法原理从末尾到首位，对每一位对齐相加即可。技巧在于如何处理不同长度的数字，以及进位和最高位的判断。这里对于不同长度的数字，我们通过将较短的数字补0来保证每一位都能相加。递归写法的思路比较直接，即判断该轮递归中两个ListNode是否为null。
全部为null时，返回进位值
有一个为null时，返回不为null的那个ListNode和进位相加的值
都不为null时，返回 两个ListNode和进位相加的值
来源一位大佬https://segmentfault.com/a/1190000002986101
原来是小学内容小学数学中学习的加法，使用递归写法。
递归，就是在运行的过程中调用自己。
什么鬼啊，自己使用自己吗？
目前我找到的对递归最恰当的比喻，就是查词典。
我们使用的词典，本身就是递归，为了解释一个词，需要使用更多的词。
当你查一个词，发现这个词的解释中某个词仍然不懂，于是你开始查这第二个词，可惜，第二个词里仍然有不懂的词，于是查第三个词，这样查下去，直到有一个词的解释是你完全能看懂的，那么递归走到了尽头，然后你开始后退，逐个明白之前查过的每一个词，最终，你明白了最开始那个词的意思。。。
好像明白了一点点~
3、解法 #（Python）
版本1
class Solution:
def addTwoNumbers(self, l1, l2):
addends = l1, l2
dummy = end = ListNode(0)
carry = 0
while addends or carry:
carry += sum(a.val for a in addends)
addends = [a.next for a in addends if a.next]
end.next = end = ListNode(carry % 10)
carry /= 10
return dummy.next
版本2
class Solution:
# @return a ListNode
def addTwoNumbers(self, l1, l2):
carry = 0
sum = ListNode(0)
s = sum
while l1 is not None or l2 is not None or carry:
s.val = carry
if l1:
s.val += l1.val
l1 = l1.next
if l2:
s.val += l2.val
l2 = l2.next
carry = s.val / 10
s.val = s.val % 10
if l1 or l2 or carry:
s.next = ListNode(0)
s = s.next
return sum
好吧，承认版本1看不懂。至于版本2 ListNode 是一个元祖，然后。。。s.val是什么意思啊？又不懂。回去看看，原来是已经定义了ListNode
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
也就是说有2个类，Solution 和 ListNode
今天先这样了，我需要去学习一下什么是“类”，也就是Python的面向对象编程
