题解 | #两个链表生成相加链表#

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

解题思路：链表加法，高位在开始位置；生成新链表

1. 解题工具

• 栈
• 虚拟头节点
• 倒插法构建链表

2. 按位相加算法

• 链表倒序存储，使用栈结构

stack = []
while head:
	stack.append(head.val)
    head = head.next

• 低位到高位按位加法

carry,val # 存储进位,当前位的和
while stack1 or stack2 or carry !=0: # 有链表不为空或有进位
	if len(stack1) > 0: # stack2相同操作
    val += stack1.pop()
    carry = val // 10
    val = val % 10
  	cur = ListNode(val)

• 倒插法构建新链表

while 外，dummy = ListNode(-1)
while 内 cur.next = dummy.next
		 dummy.next = cur