今天学习第2题两数相加,这个题目特别经典,经常在面试中出现,如果面临秋招或春招的小伙伴们最好在面试前将该题能够手写出来。这个题虽然难度为中等,但理解起来不是很困难,借助正文中的图文分析,相信大家一定能理解并测试通过。
给出两个非空的链表用来表示两个非负的整数。其中,它们各自的位数是按照逆序的方式存储的,并且它们的每个节点只能存储一位数字。 如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。 注意:您可以假设除了数字0之外,这两个数都不会以0开头。
示例:
输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)输出:7 -> 0 -> 8原因:342 + 465 = 807
这个题理解起来难度不大,就是将数字从个位数开始将数字放到链表的各个结点上,如下图所示:
然后两个链表的对应位置上的数字相加,将相加的值保存到结果链表中。这里需要注意两个关键点:一是如果两个值相加大于9该怎么办?二是两个链表长度不一致该怎么办?
carry
,当两数之和大于9时将 carry
标识为1,否则表示为0。 下面分析一个具体实例,该实例包含上述两个关键点,如下图所示:
如上图所示,数字342的链表较短,数字7465的链表较长。当两个数字的第二个结点相加时,它们的和为10,这时就需要进位,即 carry=1
,且将个位数保留作为结果链表的值。当较短的链表指向为 null
结点时,较长的链表指向的值为7,这需要将较短链表的值设置为0,即结果为0+7。 通过上面分析后,再看看如下 java
便一目了然。
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { // 创建结果链表的头节点,默认该节点中的value为-1 ListNode dummy = new ListNode(-1); ListNode pre = dummy; // 进位标识carry,默认为0 int carry = 0; // 遍历链表,当两个链表都为空时,退出 while(l1 != null || l2 != null){ // 判断该节点是否为空,当结点为空时,用0补齐; // 不为空时,加数即为节点的值 int d1 = (l1 == null) ? 0 : l1.val; int d2 = (l2 == null) ? 0 : l2.val; // 对结点求和,注意:求和是需要考虑到进位 int sum = d1 + d2 + carry; // 更新进位标识 carry = (sum >= 10) ? 1 : 0; // sum%10标识求和的个位数,将其保存到结果链表中 pre.next = new ListNode(sum % 10); pre = pre.next; if(l1 != null) l1 = l1.next; if(l2 != null) l2 = l2.next; }
// 重点,这是一个特殊情况,当两个链表计算完后, // 还需要判断进位标识是否为1,如果为1,如23+81=104,需要创建一个结点保存最高位 if(carry == 1) pre.next = new ListNode(1);
return dummy.next; }}
对于时间复杂度和空间复杂度,该题都为O(n)。
LeetCode-2 两数相加:https://github.com/JacobLei/leetcode/blob/master/src/main/java/A2_AddTwoNumbers.java
https://leetcode-cn.com/problems/add-two-numbers/solution/liang-shu-xiang-jia-by-leetcode/