LeetCode100之两数相加(2)--Java

1.问题描述

        给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。请你将两个数相加，并以相同形式返回一个表示和的链表。

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

        示例1

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

        示例2 

输入：l1 = [0], l2 = [0]
输出：[0]

        示例3 

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

        提示

• 每个链表中的节点数在范围 [1, 100] 内
• 0 <= Node.val <= 9
• 题目数据保证列表表示的数字不含前导零

        难度等级

            中等

        题目链接

                两数相加

2.解题思路

        这道两数相加的题目，有点想我们小学的时候学的那个两个数的笔算，向加个位，再加十位，这样不断的加下去，大于10就进一。

        在正式开始相加之前，我们可以先做一个判断，如果其中一个链表为空，那就直接返回另一个链表就行了。

        //如果其中一个链表为空，直接返回另一个链表
        if(l1 == null){
            return l2;
        }
        if(l2 == null){
            return l1;
        }

        接着，我们分别给两个链表定义一个用于遍历的指针，再给存储答案的链表定义一个头节点和遍历用的指针，因为相加会有进位，所以我们还需要一个存储进多少位的变量。

        //遍历两个链表的指针
        ListNode p1 = l1;
        ListNode p2 = l2;
        //答案链表的头结点
        ListNode data = null;
        //答案链表的指针
        ListNode p = null;
        //存储进位的位数
        int digit = 0;

        然后，我们就可以开始相加了。两个链表指针当前所指的节点的值相加，再加上今晚的值，就是当前位相加的总和，接着我们对这个总和做除法，除以10就得到要想下一位进多少位了。

            //计算两个节点的和
            int sum = p1.val + p2.val + digit;
            //更新进位信息
            digit = sum / 10;

        如果是第一次相加，答案链表这时候还是为空，我们要初始化答案链表，当前位的值是当前位相加的总和跟10取模，因为我们每一个位只能是0-9。同时更新答案链表的指针和两个相加链表的指针。

            //如果答案链表的头结点为空
            if(data == null){
                data = new ListNode(sum % 10);
                p = data;
            }
            //移动到下一位进行相加
            p1 = p1.next;
            p2 = p2.next;

        如果不是第一次相加，那么直接创建一个新的节点作为当前答案链表指针所指节点的下一个节点，值也是当前位相加的总和跟10取模，接着更新答案链表的指针和两个相加链表的指针即可。

                p.next = new ListNode(sum % 10);
                p = p.next;
                //移动到下一位进行相加
                p1 = p1.next;
                p2 = p2.next;

        当两个相加链表其中一个加完后，我们还需要将剩余的那个链表加到答案链表中。

         //如果链表1还有剩余的数
        while(p1 != null){
            int sum = p1.val + digit;
            digit = sum / 10;
            p.next = new ListNode(sum % 10);
            p = p.next;
            p1 = p1.next;
        }
        //如果链表2还有剩余的数
       while(p2 != null){
            int sum = p2.val + digit;
            digit = sum / 10;
            p.next = new ListNode(sum % 10);
            p = p.next;
            p2 = p2.next;
        }

        完成了两个相加链表的相加之后，我们还要注意检查最后还有没有进位，有进位的话，要将进位的那个节点不到答案链表中。

        //如果还要进位，则补充一个节点
        if(digit != 0){
            p.next = new ListNode(digit);
        }

        最后，返回答案链表的头结点即可。

3.代码展示

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        //如果其中一个链表为空，直接返回另一个链表
        if(l1 == null){
            return l2;
        }
        if(l2 == null){
            return l1;
        }
        //遍历两个链表的指针
        ListNode p1 = l1;
        ListNode p2 = l2;
        //答案链表的头结点
        ListNode data = null;
        //答案链表的指针
        ListNode p = null;
        //存储进位的位数
        int digit = 0;
        //开始相加
        while(p1 != null && p2 != null){
            //计算两个节点的和
            int sum = p1.val + p2.val + digit;
            //更新进位信息
            digit = sum / 10;
            //如果答案链表的头结点为空
            if(data == null){
                data = new ListNode(sum % 10);
                p = data;
            }else{
                p.next = new ListNode(sum % 10);
                p = p.next;
            }
            //移动到下一位进行相加
            p1 = p1.next;
            p2 = p2.next;
        }
        //如果链表1还有剩余的数
        while(p1 != null){
            int sum = p1.val + digit;
            digit = sum / 10;
            p.next = new ListNode(sum % 10);
            p = p.next;
            p1 = p1.next;
        }
        //如果链表2还有剩余的数
       while(p2 != null){
            int sum = p2.val + digit;
            digit = sum / 10;
            p.next = new ListNode(sum % 10);
            p = p.next;
            p2 = p2.next;
        }
        //如果还要进位，则补充一个节点
        if(digit != 0){
            p.next = new ListNode(digit);
        }
        //将结果返回
        return data;
    }
}

4.总结

        这道题给我的感觉就像小时候做的两位数加法的笔算，只是将笔算的过程用链表和代码模拟出来而已，需要注意的是，最后还要做一次是否要进位的判断，这里是一个小坑。好了，今天这道题就啰嗦到这，祝大家刷题愉快~