2. 两数相加
给定两个非空链表来表示两个非负整数。位数按照逆序方式存储，它们的每个节点只存储单个数字。将两数相加返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。
示例:
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
解法1:
常规思路, 关键点: 头结点, 进位, 链表长度不一致时
class Solution:
def addTwoNumbers(self, l1, l2):
carry = 0 #进位值
isFirst = True #头结点flag
currentNode = None #当前结点
head = None #头结点
while (l1 or l2 or carry != 0): #循环条件: l1, l2的遍历没结束, 或有高位进位时
val1 = 0
val2 = 0
if l1:
val1 = l1.val
l1 = l1.next
if l2:
val2 = l2.val
l2 = l2.next
unit = val1 + val2 + carry
if unit >= 10:
carry = 1
unit = unit%10
else:
carry = 0
node = ListNode(unit)
if isFirst:
currentNode = node
head = currentNode
isFirst = False
else:
currentNode.next = node
currentNode = currentNode.next
return head
解法2
给定一个空的头结点, 简化代码.
class Solution:
def addTwoNumbers(self, l1, l2):
head = ListNode(0) #头结点设为空结点
current = head
carry = 0
while (l1 or l2 or carry !=0):
if l1:
carry += l1.val
l1 = l1.next
if l2:
carry += l2.val
l2 = l2.next
node = ListNode(carry%10)
carry = carry//10
current.next = node
current = current.next
return head.next
