LeetCode刷题第二天

2.给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

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

输出：7 -> 0 -> 8

原因：342 + 465 = 807

大意解析：先整明白题目到底啥意思，两个非空的链表将两个非负的整数逆序存储，根据示例将相加的后的结果逆序排列

 /**

  * 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) {
　　　　　　　//定义哑结点，哑节点（dummy node）是初始值为NULL的节点，哑结点的引入可以解决头结点为空的情况

         ListNode dummyHead  = new ListNode(0);
　　　　　　　//　p,q 分别为链表1，链表2的指针,当前节点初始化为哑结点

         ListNode p = l1, q = l2, current = dummyHead;
　　　　　　//进位标志

         int carry = 0;

         while(p!= null || q!= null){

             int x = (p!= null) ? p.val : 0;

             int y = (q!= null) ? q.val : 0;

             int sum = x + y + carry;
　　　　　　　　　//更新进位标志

             carry = sum / 10 ;
　　　　　　　　//将相加的结果赋值

             current.next = new ListNode(sum%10);
　　　　　　　　　//指针后移一位

             current = current.next;

             if(p!=null) p = p.next;

             if(q!=null) q = q.next;

         }

         if(carry>0){
　　　　　　　　//如果进位为1，就要加上1

             current.next = new ListNode(carry);

         }
　　　　　　返回结果链表

         return dummyHead.next;

     }

 }

很精致的答案
学到的知识
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的新结点。
返回哑结点的下一个结点。

巴特西

LeetCode刷题第二天

最新文章

热门文章