LeetCode刷题心得——两数相加

0.前言1.题目介绍2.题目分析3.题目解答4.总结

0.前言

这是我刷LeetCode的第二题,是一道中等难度的题目,用到的是数据结构中的单链表的知识,这一块当时学的时候就不咋地,是真的不会做.看了答案解析之后,摸索着把代码写了出来.

1.题目介绍

//给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。 // // 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。 // // 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。 // // 示例： // // 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4) //输出：7 -> 0 -> 8 //原因：342 + 465 = 807 // // Related Topics 链表 数学 //leetcode submit region begin(Prohibit modification and deletion) /** * 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) { } //leetcode submit region end(Prohibit modification and deletion)

2.题目分析

简单来说就是,给定两个数,这两个数的各个位上的数字用单链表的节点表示,val表示数值,next表示下一位. 这道题目我刚刚拿到有点不理解,说好的给定一个单链表,但实际上给的变量是两个对应位上的节点,后来我明白了,这个给定的节点因为有next作为下一个节点的指针,实际上给的是一个连一个的单链表. 题目给出了单链表的具体类

class ListNode { int val; ListNode next; ListNode(int x) { val = x; }

这里我个人建议在leetcode submit region end(Prohibit modification and deletion)区域外定义一下这个节点类,这样写起来方便一些.不要在这个区域里定义,因为这个区域内的代码都会提交的. 按照题目的要求,我只要把两个节点的数值相加赋值给最终结果节点即可.但有一个问题,就是进位怎么办? 因此需要一个变量表示进位的数值,然后在下一位相加的时候把进位也加上.还需要考虑一种情况,如果是三位数+两位数的情况怎么办?这时候就需要先判断一下当前节点是否为空,如果为空,则需要把当前节点的数值当成0,这样的话,还需要考虑循环终止的条件,条件应该为两个节点都为空时终止循环.返回结果.暂时就先想到这里,把代码写一写.

public ListNode addTwoNumbers(ListNode l1, ListNode l2) { //头结点,head.next指向个位 ListNode head = new ListNode(0); //最终的结果,因为head在循环过程中会更改位置,因此需要提前保存当前节点(next指向个位的节点) ListNode result = head; //进位的数值 int carry = 0; //循环终止条件,l1和l2都为空时才终止 while (l1 != null || l2 != null) { //一种方便的写法,如果满足l1=null,则返回冒号前面的,反之返回冒号后面的 int x = l1 == null ? 0 : l1.val; int y = l2 == null ? 0 : l2.val; //相加的数值 int sum = x + y + carry; //head的next的指针指向一个新的节点,数值为sum%10 head.next = new ListNode(sum % 10); //进位carry等于sum/10 carry = sum / 10; //如果l1!=null,需要移动指针,继续向下一位相加 //如果l1==null,久没有l1.next了 if (l1 != null) { l1 = l1.next; } if (l2 != null) { l2 = l2.next; } //head指针移动,继续计算下一位的数值 head = head.next; } //相当于最开始的头结点的next指针指向的节点(结果链表的个位) return result.next; }

具体内容都在注释里写明了,感觉写的还是比较清楚的. 下面提交运行一下出了一点问题 会这样报错,你估计会有疑问,为啥期望结果会是两个数呢? 考虑这样一种情况,假设500+500,最终结果为1000,因为之前的判断是只要两个三位数的最高位的下一位为空就停止循环,但这样的话,这第四位就没有存储,因此在第三位的时候就必须得在第三位的next指针指向一个新建的节点,该节点数值为进位,这点不容易想到.但测试之后仔细琢磨应该能明白. 具体实现方法大概就是,先判断是否有进位(carry==1),如果有则,把当前节点的next指针指向一个新节点,数值为carry,如果当前位不是最高位,下一次循环会对这个节点的数值覆盖,如果是最高位,没有了下一次循环就把这个节点值保存了下来.这段代码的位置,应该在head=head.next之后执行,这样才能保证是进位.

3.题目解答

public ListNode addTwoNumbers(ListNode l1, ListNode l2) { //头结点,head.next指向个位 ListNode head = new ListNode(0); //最终的结果,因为head在循环过程中会更改位置,因此需要提前保存当前节点(next指向个位的节点) ListNode result = head; //进位的数值 int carry = 0; //循环终止条件,l1和l2都为空时才终止 while (l1 != null || l2 != null) { //一种方便的写法,如果满足l1=null,则返回冒号前面的,反之返回冒号后面的 int x = l1 == null ? 0 : l1.val; int y = l2 == null ? 0 : l2.val; //相加的数值 int sum = x + y + carry; //head的next的指针指向一个新的节点,数值为sum%10 head.next = new ListNode(sum % 10); //进位carry等于sum/10 carry = sum / 10; //如果l1!=null,需要移动指针,继续向下一位相加 //如果l1==null,久没有l1.next了 if (l1 != null) { l1 = l1.next; } if (l2 != null) { l2 = l2.next; } //head指针移动,继续计算下一位的数值 head = head.next; //如果进位为1,则需要新建一个节点表示,如果不是最高位,后续会对当前数值覆盖 //而如果当前是最高位,就会产生一个新的节点,而不会被后续覆盖 if (carry == 1) { head.next = new ListNode(carry); } } //相当于最开始的头结点的next指针指向的节点(结果链表的个位) return result.next; }

这样,这道题目就算是完成了.

4.总结

说实话,最开始这道题目我是真的不会,因为当时学数据结构的时候,链表这一块我不太懂,经过这道题的钻研,我大致弄明白了单链表.虽然是看了参考答案才明白的,但最终代码是我自己根据自己对解析的理解写的,并且思路也在上文阐述了,基本上算是搞明白了这道题.LeetCode真的不简单,数据结构基础太重要了.