牛客网高频算法题系列-BM11-链表相加(二)

题目描述

假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。给定两个这种链表，请生成代表两个整数相加值的结果链表。

原题目见：BM11 链表相加(二)

解法一：使用栈

首先，特殊情况判断：

• 如果链表一为空，则直接返回链表二

• 如果链表二为空，则直接返回链表一

否则，使用2个栈用来存放两个链表的结点：

• 首先将两个链表中的结点添加到栈中；

• 遍历2个栈，即执行加法，将值添加到新的栈中这样可以按倒序进行结点值相加，其中需要使用一个变量记录进位值；

• 需要注意的是，遍历结束后，需要根据进位值判断是否需要添加额外的结点；

• 最后，根据新的栈构造相加后的链表并返回之。

如果不想使用多余的栈空间，可以考虑先将两个链表倒序排列后，再执行加法。

代码

1.01^{365} ≈ 37.7834343329   

0.99^{365} ≈ 0.02551796445   

相信坚持的力量！