Leetcode 445. 两数相加 II ----python

本文主要是介绍Leetcode 445. 两数相加 II ----python，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 题目描述

给定两个非空链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储单个数字。将这两数相加会返回一个新的链表。

你可以假设除了数字 0 之外，这两个数字都不会以零开头。
示例:
输入: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
输出: 7 -> 8 -> 0 -> 7

2. 解题思路

此题若不逆置初始链表，可以用栈来存储链表的值，然后相加，再把相加后的值存在新链表中。
步骤：
（1）用两个栈（stack1，stack2）分别存下两个链表的值
（2）从两个栈中取出元素，相加，相加后放在新的栈（stack3）中
（3）把新栈里的元素放入链表

3.代码实现

class Solution:def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:stack1 = []stack2 = []stack3 = []# 将两链表的元素分别入栈while(l1):stack1.append(l1.val)l1 = l1.nextwhile(l2):stack2.append(l2.val)l2 = l2.nextlend = 0# 将两链表的元素相加后，入栈while(stack1 and stack2):temp = stack1.pop(len(stack1)-1) + stack2.pop(len(stack2)-1)+ lendif(temp < 10):stack3.append(temp)lend = 0else:stack3.append(int(str(temp)[1]))lend = 1while(stack1 == [] and  stack2 != []):temp = stack2.pop(len(stack2)-1)+ lendif(temp < 10):stack3.append(temp)lend = 0else:stack3.append(int(str(temp)[1]))lend = 1while(stack2 == [] and  stack1 != []):temp = stack1.pop(len(stack1)-1) + lendif(temp < 10):stack3.append(temp)lend = 0else:stack3.append(int(str(temp)[1]))lend = 1if(lend == 1):stack3.append(1)#将栈的值放入链表dummy = ListNode(None)head = dummyfor i in stack3[::-1]:node = ListNode(i)head.next = nodehead = head.nextreturn dummy.next

在这里插入图片描述

4. 测试用例和测试结果

测试用例

# Definition for singly-linked list.
class ListNode:def __init__(self, x):self.val = xself.next = Noneclass Solution:def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:stack1 = []stack2 = []stack3 = []# 将两链表的元素分别入栈while(l1):stack1.append(l1.val)l1 = l1.nextwhile(l2):stack2.append(l2.val)l2 = l2.nextlend = 0# 将两链表的元素相加后，入栈while(stack1 and stack2):temp = stack1.pop(len(stack1)-1) + stack2.pop(len(stack2)-1)+ lendif(temp < 10):stack3.append(temp)lend = 0else:stack3.append(int(str(temp)[1]))lend = 1while(stack1 == [] and  stack2 != []):temp = stack2.pop(len(stack2)-1)+ lendif(temp < 10):stack3.append(temp)lend = 0else:stack3.append(int(str(temp)[1]))lend = 1while(stack2 == [] and  stack1 != []):temp = stack1.pop(len(stack1)-1) + lendif(temp < 10):stack3.append(temp)lend = 0else:stack3.append(int(str(temp)[1]))lend = 1if(lend == 1):stack3.append(1)#将栈的值放入链表（新开辟的链表空间）dummy = ListNode(None)head = dummyfor i in stack3[::-1]:node = ListNode(i)head.next = nodehead = head.nextreturn dummy.next#打印链表操作def printLink(self,root):r = rootwhile(r):print(r.val)r = r.nextroot1 = ListNode(9)
n2 = ListNode(4)
n3 = ListNode(6)
root1.next = n2
n2.next = n3root2 = ListNode(0)
# r2 = ListNode(5)
# r3 = ListNode(7)
# root2.next = r2
# r2.next = r3s = Solution()
result= s.addTwoNumbers(root1,root2)
s.printLink(result)

测试结果：