题目描述
给定两个非空链表来表示两个非负整数。位数按照逆序方式存储，它们的每个节点只存储单个数字。将两数相加返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头
示例
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
测试用例
[2,4,3]
[5,6,4]
[1]
[9,9]
[5]
[5]
[0]
[7,3]
[9,9]
[9]
解题思路
遍历链表，按节点两两相加，有进位将进位加到下一个节点。
解题思路很简单，此题被标记为中等难度，是因为：
- 数据结构是链表；
- 两个链表长度不一定相等，尤其是有进位情况下的处理需考虑。
解答
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def addTwoNumbers(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
l3 = l1
while l1 != None or l2 != None:
sum = l1.val + l2.val
l1.val = sum % 10
if sum >= 10:
if l1.next != None:
l1.next.val = l1.next.val + 1
if l1.next.val >= 10 and l2.next == None:
l2.next = ListNode(0)
else:
l1.next = ListNode(1)
else:
if l1.next == None and l2.next != None:
l1.next = ListNode(0)
if l2.next == None:
break
l1 = l1.next
l2 = l2.next
return l3
算法分析
上述算法通过一次遍历完成，没有用单独的变量存储 carry 值。两个链表同节点相加的结果最大为 9 + 9 + 1 = 19，所以结果链表中对应节点的值永远可以用(l1[index] + l2[index] + carry) % 10来得到。
上述算法将进位 carry 计入到了下一位中。具体解题过程为
- 用新变量 l3 保留对 l1 的引用
- l1 和 l2 对应节点做加法
- 有进位且 l1 有下一节点的情况下，将进位加入到 l1 的下一个节点；l1 没有下一个节点就给 l1 添加一个值为 1 的节点；没有进位执行步骤4
- l1 没有下一个节点了，但是 l2 还有下一个节点，就给 l1 添加一个值为 0 的节点
- 3 或 4 步骤执行完毕，如果 l2 没值了，就跳出循环，返回 l3，原题得解；否则将 l1 和 l2 移动一个节点，执行步骤2
中文官网的题目地址：两数相加