共计 1327 个字符,预计需要花费 4 分钟才能阅读完成。
更多算法题解,请关注公众号【程序员学长】
两个链表生成相加链表
问题形容
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
正文完