445.两个数相加二题目来源：https://leetcode-cn.com/problems/add-two-numbers-ii题目给你两个非空链表来表示两个非负整数。数字的最高位在链表的开头。他们的每个节点只存储一个数字。将这些数字相加会返回一个新的链表。你可以假设除了数字0之外，这两个数字都不以零开头。进阶：输入链表无法修改怎么办？换句话说，您不能翻转列表中的节点。例子：输入：(7->2->4->3)+(5->6->4)输出：7->8->0->7解题思路：栈在进阶tips，它要求不修改输入链表，链表中的节点不可翻转。那么这里可以考虑使用栈，利用栈的先进后出的特性，对链表进行逆序处理。在处理栈元素返回链表时，使用head插值的方式保证返回的链表顺序正确。具体流程如下图：代码实现#单向链表的定义。#classListNode:#def__init__(self,x):#self.val=x#self.next=Noneclassself,l1:ListNode,l2:ListNode)->ListNode:#推送方法defpush_stack(node,stack):whilenode:stack.append(node.val)node=node.next#定义堆栈stack1=[]stack2=[]#执行栈操作push_stack(l1,stack1)push_stack(l2,stack2)#记录进位carry=0#dummy节点，控制链表returndummy=ListNode(0)#执行计算#终止条件：栈为空时,或者进位为0whilestack1orstack2orcarry:a,b=0,0#pop计算ifstack1:a=stack1.pop()ifstack2:b=stack2.pop()sum_=a+b+carrycarry=sum_//10mod=sum_%10#使用头部插值#将结果放入返回的链表中#这个返回的链表顺序是正确的倒序，然后解决问题《445. 两数相加 II》其中主要内容是在返回一个新的链表时，使用头部插值的方法来保证返回的链表顺序正确。欢迎关注微信公众号《书所集录》
