LeetCode-2-Add Two Numbers

这道题的题意是:给出两个链表,求这两个链表表示的数字的和,并且用一个新的链表来存这个数字并返回这个链表的头结点。

一个非常典型的错误代码如下:

上面这段代码的思路是:将这两个链表先转换成数字,然后对数字进行相加,最后再把这个数字用链表表示出来。看起来呢这种算法比较直观简单,如果用一些比较短的链表来测试的话结果也是对的,但是它的问题在于:如果链表很长很长,比如说有100个元素,那么就不能用基本类型来表示,否则就会产生溢出,造成不正确的计算结果。所以呢这个题其实是一个非常经典的大数问题。面对大数问题,我们只能一位一位地进行处理。

解决大数问题的最核心的过程就是对于进位的处理了。为了叙述的方便,假设两个输入的链表分别是A和B,输出的链表是C,那么C的第n位的数字应该是A的第n位数字加上B的第n位数字再加上前一位产生的进位。因此我们需要用一个变量标记当前位相加是否产生了进位,并且在每次相加后更新这个变量的值。剩下的内容就是一些边界情况的处理,这部分很繁琐,因此必须要非常小心,不过尝试几次后应该就可以通过了。

UPDATE:在评论区看到了更为简单的一种实现:

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据