更多算法题解，请关注公众号【程序员学长】
两个链表生成相加链表
问题形容
LeetCode 剑指 Offer II 025. 链表中的两数相加
假如链表中每一个节点的值都在 0 - 9 之间，那么链表整体就能够代表一个整数。给定两个这种链表，请生成代表两个整数相加值的后果链表。
示例：
输出：[9,3,7]，[6,3]
返回值：{1,0,0,0}
剖析问题
因为两个数字相加是从个位数开始，而后再十位数、百位数。对于的链表中，咱们须要将两个链表进行右端对齐，而后从右往左进行计算。
要想让两个链表右端对齐，咱们有两种实现形式。
- 将两个链表进行反转，而后间接求和。
- 借助栈这种先进后出的个性，来实现链表的右端对齐。
咱们先来看一下如何应用链表反转来实现。
class Solution(object): def reverse(self, head): cur = head #初始化时，pre为None pre = None while cur: next=cur.next cur.next = pre pre = cur cur = next return pre def addTwoNumbers(self, l1, l2): #将两个链表翻转 l1 = self.reverse(l1) l2 = self.reverse(l2) head=ListNode(0) pre=head #代表是否进位 carray=0 while l1 or l2: v1=l1.val if l1 else 0 v2=l2.val if l2 else 0 sum=v1+v2+carray #进位数 carray=int(sum/10) tmp=sum%10 node=ListNode(tmp) pre.next=node pre=pre.next if l1: l1=l1.next if l2: l2=l2.next if carray==1: node=ListNode(carray) pre.next=node return self.reverse(head.next)上面咱们来看一下如何应用栈来求解。咱们首先将两个链表从头到尾放入两个栈中，而后每次同时出栈，就能够实现链表的右端对齐相加，咱们来看一下代码如何实现。
def addTwoNumbers(l1, l2): #申请两个栈 stack1=[] stack2=[] #l1入栈 while l1: stack1.append(l1.val) l1 = l1.next while l2: stack2.append(l2.val) l2 = l2.next head = None carry = 0 while stack1 and stack2: num = stack1.pop() + stack2.pop() + carry #求进位数 carry=int(num/10) tmp=num%10 node = ListNode(tmp) node.next = head head = node s = stack1 if stack1 else stack2 while s: num = s.pop() + carry carry = int(num / 10) tmp = num % 10 node = ListNode(tmp) node.next = head head = node if carry==1: node = ListNode(carry) node.next = head head = node return head