【完虐算法】两个链表生成相加链表 leetcode链表算法

更多算法题解，请关注公众号【程序员学长】
两个链表生成相加链表问题描述
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=nodereturn 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.nexthead = None carry = 0while stack1 and stack2: num = stack1.pop() + stack2.pop() + carry #求进位数 carry=int(num/10) tmp=num%10 node = ListNode(tmp) node.next = head head = nodes = 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 = nodeif carry==1: node = ListNode(carry) node.next = head head = node return head