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

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.next while(l2): stack2.append(l2.val) l2 = l2.next lend = 0# 将两链表的元素相加后，入栈 while(stack1 and stack2): temp = stack1.pop(len(stack1)-1) + stack2.pop(len(stack2)-1)+ lend if(temp < 10): stack3.append(temp) lend = 0 else: stack3.append(int(str(temp)[1])) lend = 1while(stack1 == [] andstack2 != []): temp = stack2.pop(len(stack2)-1)+ lend if(temp < 10): stack3.append(temp) lend = 0 else: stack3.append(int(str(temp)[1])) lend = 1while(stack2 == [] andstack1 != []): temp = stack1.pop(len(stack1)-1) + lend if(temp < 10): stack3.append(temp) lend = 0 else: stack3.append(int(str(temp)[1])) lend = 1if(lend == 1): stack3.append(1)#将栈的值放入链表 dummy = ListNode(None) head = dummy for i in stack3[::-1]: node = ListNode(i) head.next = node head = head.next return dummy.next

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

文章图片

4. 测试用例和测试结果测试用例

# Definition for singly-linked list. class ListNode: def __init__(self, x): self.val = x self.next = Noneclass Solution: def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode: stack1 = [] stack2 = [] stack3 = [] # 将两链表的元素分别入栈 while(l1): stack1.append(l1.val) l1 = l1.next while(l2): stack2.append(l2.val) l2 = l2.next lend = 0# 将两链表的元素相加后，入栈 while(stack1 and stack2): temp = stack1.pop(len(stack1)-1) + stack2.pop(len(stack2)-1)+ lend if(temp < 10): stack3.append(temp) lend = 0 else: stack3.append(int(str(temp)[1])) lend = 1while(stack1 == [] andstack2 != []): temp = stack2.pop(len(stack2)-1)+ lend if(temp < 10): stack3.append(temp) lend = 0 else: stack3.append(int(str(temp)[1])) lend = 1while(stack2 == [] andstack1 != []): temp = stack1.pop(len(stack1)-1) + lend if(temp < 10): stack3.append(temp) lend = 0 else: stack3.append(int(str(temp)[1])) lend = 1if(lend == 1): stack3.append(1)#将栈的值放入链表（新开辟的链表空间） dummy = ListNode(None) head = dummy for i in stack3[::-1]: node = ListNode(i) head.next = node head = head.next return dummy.next#打印链表操作 def printLink(self,root): r = root while(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)

测试结果：