题目描述
用两个非单空链表逆序的表示两个非负整数，链表中的每个节点存储数字中的一个数位，链表起始节点表示个位、第二个节点表示十位….，最后一个节点表示最高位。除了数字 0 之外，这两个数字都不会以 0 开头。
图示如下：
单链表1：2 -> 4 -> 3
单链表2：5 -> 6 -> 4
表示数字 342 和 465。
要求输入两个链表的头节点，以相同形式输出这两个数相加的结果。
示例：
输入：l1 = [2, 4, 3] l2 = [5, 6, 4]
输出：[7, 0, 8]
解释：342 + 465 = 807
理解
观察链表的表示可以发现这种表示方式中，链表头节点是最低位，尾节点是最高位。并且有前提“两个数字除了 0 之外，都不会以 0 开头“，这说明两个数的数位正好是对齐的。如果以两个指针从前往后同步遍历两个链表，则个位对个位，十位对十位。运算时，只要将对应指针指向的节点的数值相加，超过 10 的则用一个临时变量存储 1 表示进位，下一次循环中加上这个进位的 1。要注意，产生进位后，当前节点值的和应减去 10。
另外，有可能两个链表长度不一致，而且有可能最后一位的运算会产生进位，所以结束循环的条件应该是两个指针均指向空且上一次加法中没有产生进位，即存储进位的临时变量值 != 1。
代码实现
Python3 代码实现如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
nodeIndex1 = l1
nodeIndex2 = l2
l3 = None
nodeIndex3 = None
tempVal = 0
while nodeIndex1 != None or nodeIndex2 != None or tempVal != 0:
tempNode = ListNode(0, None)
val1 = nodeIndex1.val if nodeIndex1 else 0
val2 = nodeIndex2.val if nodeIndex2 else 0
val3 = val1 + val2 + tempVal
if (val3 >= 10):
tempVal = 1
val3 = val3 - 10
else:
tempVal = 0
tempNode.val = val3
if l3 is None:
l3 = tempNode
nodeIndex3 = l3
else:
nodeIndex3.next = tempNode
nodeIndex3 = nodeIndex3.next
nodeIndex1 = nodeIndex1.next if nodeIndex1 else None
nodeIndex2 = nodeIndex2.next if nodeIndex2 else None
return l3
|