本文共 2444 字，大约阅读时间需要 8 分钟。
先放题目
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 -> 8Explanation: 342 + 465 = 807.
解释：
题意：存在两个非负整数，数字以相反的顺序存储，每一个节点表示一个数字，添加两个数字，并使其相加答案作为链表输出
输入输出：
上述例子表示342+465=807，第一次输入2，5，输出为7，第二次输入4，6，相加为10，取个位输出为0，第三次输入3，4，输出为8，包括3+4和第二次输入结果的十位数1。
代码：class Solution(object): def addTwoNumbers(self, l1, l2): """ :type l1: ListNode :type l2: ListNode :rtype: ListNode """ resultnode = None ＃将每次输入结果先存储为空节点 add = 0 ＃表示进位的结果，如上述输入输出中的十位数1 while True: ＃这里是为了简化计算，由于是两个非负数相加，如果为2345+345，则两个链表长度不一致，这时将345末尾补0，当两条链表末尾都是－1时，表示运算结束 if l1.val == -1: l1.val = 0 if l2.val == -1: l2.val = 0 tSum = (l1.val + l2.val + add) % 10 ＃表示两位数相加，取个位数 add = (l1.val + l2.val + add) / 10 ＃若存在进位，更新add的值 listn = ListNode(tSum) ＃将tSum记录进链表，这里的ListNode是LeetCode以存在的函数，将tSum转化为节点 if resultnode ==None: ＃如果结果为空时，直接存储在链表中 resultnode = listn flagnode = resultnode else: ＃如果结果不为空时，存储在下一个节点中 flagnode.next = listn flagnode = flagnode.next if l1.next != None:＃当链表下一个节点不为空时，更新l1(l2)的值，否则存储为空,当均为空时，直接退出函数 l1 = l1.next else: l1.val = -1 if l2.next != None: l2 = l2.next else: l2.val = -1 if l1.val == -1 and l2.val == -1: break if add != 0 : ＃处理进位值，如最后值为7+8，则需要增加一个节点存储进位值 listn = ListNode(add) flagnode.next = listn return resultnode调试代码：
if __name__=='__main__': print "-------------start-------------" l1_1 = ListNode(2) l1_2 = ListNode(4) l1_3 = ListNode(3) l1_1.next = l1_2 l1_2.next = l1_3 l2_1 = ListNode(5) l2_2 = ListNode(6) l2_3 = ListNode(4) l2_1.next = l2_2 l2_2.next = l2_3 l3_1 = Solution().addTwoNumbers(l1_1,l2_1) while l3_1 != None: print l3_1.val l3_1 = l3_1.next输出结果：
python leetcodetest.py-------------start-------------708
转载地址：http://vwhci.baihongyu.com/