相加得到两个非空链表，表示两个非负整数。其中，它们各自的位数倒序存储，它们的每个节点只能存储一位数。如果，我们将这两个数字相加，将返回一个新的链表来表示它们的和。您可以假设除了数字0之外，这两个数字都不以0开头。示例：输入：(2->4->3)+(5->6->4)输出：7->0->8原因：342+465=807来源：LeetCode链接：https://leetcode-cn.com/probl...版权归灵口网所有。商业转载请联系官方授权，非商业转载请注明出处。分析这道题的本质是两个数相加。两个数按照各自的位数组成一个链表。两位数的位数分别为l1和l2。每个对应数字的最大和为9+9+1=19。1为上位溢出，溢出的每一位为0或1。即求和的每一位为t(x)=l1(x)+l2(x)+carrycarry解决前一位溢出的问题#单向链表的定义.#classListNode(object):#def__init__(self,x):#self.val=x#self.next=Noneclass解决方案(object):defaddTwoNumbers(self,l1,l2):""":typel1:ListNode:typel2:ListNode:rtype:ListNode"""result=ListNode(0)carry=0next_node=resultwhile(l1isnotNone)or(l2isnotNone):ifl1isnotNone:l1_val=l1.vall1=l1.nextelse:l1_val=0如果l2不是None:l2_val=l2.vall2=l2.nextelse:l2_val=0temp=l1_val+l2_val+carrycarry=temp//10current_value=temp%10next_node.next=ListNode(current_value)next_node=next_node.next#如果要对两个数的最大位加溢出，则进位ifcarry==1:next_node.next=ListNode(carry)returnresult.next算法最多需要循环到两个数中较长的数来完成，因此算法复杂度为O(max(m,n))，结果的最大长度为max(m,n)+1，所以算法空间复杂度为O(m,n)+1
