Leetcode 第2题 Add Two Numbers题解 (Java)

原题地址:https://leetcode.com/problems/add-two-numbers/

难度:中级

题目:

这题的基本意思是,给你两个非空的链表表示了两个正整数。每一个节点表示一位数字,按照反序(个位数在最前面)。把两个数字加起来,返回一个代表和的链表。

你可以假设这两个数字都不带前导0,除非0这个数字本身。

示例为:

输入:(2 -> 4 -> 3) + (5 -> 6 ->4)

输出:7 ->0 -> 8

解释:342 + 465 = 807

题目很好理解,而且链表已经反序计算起来并不难,两个数字的位数可能不同,如果高位在前,我们硬从高位算起还需要对齐。从低位算起就很简单。事实上,这跟我们小时候用竖式做加法很像,我们举例如下:

如果你还记得小时候学竖式加法,其实就是从最后一位加起,两个数字相加,如果不超过10,结果直接写在结果的位置上,如果超过10则在前面加上一个进位标记。也就是我在图中,4和6之间放的标记。然后如果所在位置已经有进位符号则两个数字相加后,再加一。我们小学就都学习这个了。这不难,其实就是把这个逻辑翻译成代码即可,而且这个题,我想象不出什么加速方法,就这么一位一位的加效率就一定是很高的,其实就是同时遍历两个链表,取出当前位置的数字,相加,如果某一个链表已经穷尽,则直接输出另外一个链表的数字。如果两个链表都穷尽,则运算完成。

现在我们看代码:

这道题并不难,算不上中间,最多就是Easy。时间复杂度是O(n)。我的提交时间是19ms,在java提交中打败了98.07%的提交者。

本文对应的代码在我的Github可以找到 https://github.com/tinyfool/leetcode/tree/master/src/p0002

打赏

发表评论

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

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