2.给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。
如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外,这两个数都不会以 0 开头。
示例:
输入:(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出:7 -> 0 -> 8 原因:342 + 465 = 807
大意解析:先整明白题目到底啥意思,两个非空的链表将两个非负的整数逆序存储,根据示例将相加的后的结果逆序排列
1 /** 2 * Definition for singly-linked list. 3 * public class ListNode { 4 * int val; 5 * ListNode next; 6 * ListNode(int x) { val = x; } 7 * } 8 */ 9 class Solution { 10 public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
//定义哑结点,哑节点(dummy node)是初始值为NULL的节点,哑结点的引入可以解决头结点为空的情况 11 ListNode dummyHead = new ListNode(0);
// p,q 分别为链表1,链表2的指针,当前节点初始化为哑结点 12 ListNode p = l1, q = l2, current = dummyHead;
//进位标志 13 int carry = 0; 14 while(p!= null || q!= null){ 15 int x = (p!= null) ? p.val : 0; 16 int y = (q!= null) ? q.val : 0; 17 int sum = x + y + carry;
//更新进位标志 18 carry = sum / 10 ;
//将相加的结果赋值 19 current.next = new ListNode(sum%10);
//指针后移一位 20 current = current.next; 21 if(p!=null) p = p.next; 22 if(q!=null) q = q.next; 23 } 24 if(carry>0){
//如果进位为1,就要加上1 25 current.next = new ListNode(carry); 26 }
返回结果链表 27 return dummyHead.next; 28 29 } 30 }
很精致的答案
学到的知识
1 三元运算符
Int A,B,C;
A=2;
B=3;
C=A>B ? 100 :200;
这条语句的意思是,如果A>B的话,就将100赋给C,否则就将200赋给C;
2 取余取整
7/2 为3 取整
7%2 为1 取余
3 整体思路
计算两个数字的和,首先从最低有效位也就是列表 l1和 l2的表头开始相加。
由于每位数字都应当处于 0…9 的范围内,我们计算两个数字的和时可能会出现“溢出”。例如,5+7=12。
在这种情况下,我们会将当前位的数值设置为 2,并将进位 carry=1 带入下一次迭代。
进位 carry必定是 0或 1,这是因为两个数字相加(考虑到进位)可能出现的最大和为 9 + 9 + 1 = 19
-
- 将 x设为结点 p的值。如果 p 已经到达 l1 的末尾,则将其值设置为 0。
- 将 y 设为结点 q 的值。如果 q 已经到达 l2 的末尾,则将其值设置为 0。
- 设定 sum = x + y + carry
- 更新进位的值,carry = sum / 10
- 创建一个数值为 (sum bmod 10)的新结点,并将其设置为当前结点的下一个结点,然后将当前结点前进到下一个结点。
- 同时,将 p 和 q 前进到下一个结点。
- 检查 carry = 1是否成立,如果成立,则向返回列表追加一个含有数字 1的新结点。
- 返回哑结点的下一个结点。
内容来源于网络如有侵权请私信删除
- 还没有人评论,欢迎说说您的想法!