2. 两数相加 ------- leetcode刷题

小王不头秃

发布于 2024-06-19 16:49:50

980

发布于 2024-06-19 16:49:50

文章被收录于专栏：后端/图像融合/机器学习/爬虫后端/图像融合/机器学习/爬虫

题目

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

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

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

题解

首先先分析一下题目，我们可以知道所有的数都是倒着放在链表中，例如 123 在链表中的存放方式就是 321，此时个位就在第一个节点，十位在第二个节点，依次类推

题目中需要我们做的就是将两个链表中存储的数据进行加和，然后再以这种倒着的方式存入新的链表中，博主最开始的思想是将两个链表进行逆向输出凑成两个整数再加和，然后放入新链表中，但是数字太大，我们承受不住

接下来就是正确的姿势来结题了，我们可以想象一下我们是如何进行加法运算的

从个位开始加，如果大于等于10就向十位加个1
十位在进行加法，但不要忘记进位，再进行步骤1中的判断依次类推，直到每一位上的数字都处理完毕

这里有几个注意的点

两个数若长度相同，需要判断最高位加和之后是否产生进位，若产生进位，需要在新链表中新增一个节点，放入进位值
两个数若长度不同，需要判断长短，长的那一条剩余的节点在并入最终的链表时也要判断是否上一位产生进位
若产生进位则需要在剩余链表的第一个节点再加上进位，然后再判断是否产生进位加入下一位，直至结束，如果最后仍有进位，需要在尾部创建新节点，放入进位值
若未产生进位则直接并入最终的链表中即可

大致的过程如上所述，接下来就开始写代码了，博主是用java写的，c++太久没用了，全给忘了

完整代码

/**
 * 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) {
        int sum = 0;
        ListNode head = new ListNode();
        ListNode p = head;   //这里创建了头节点方便操作
        int extra = 0;
        while (l1 != null && l2 != null) {
            sum = l1.val + l2.val + extra;
            extra = 0;
            p.next = new ListNode();
            p = p.next;
            p.val = sum % 10;
            if (sum > 9) {    //判断是否产生进位
                extra = 1;
            }
            l1 = l1.next;
            l2 = l2.next;
        }
        ListNode temp = null; //记录长链表的第一位
        ListNode temp2 = null; //做为链表游标进行移动的
        //判断哪个表比较长
        if (l1 != null) {
            temp = l1;
            temp2 = l1;
        }
        if (l2 != null) {
            temp = l2;
            temp2 = l2;
        }
        if (temp2 != null) {     //两个数长度不同才会执行
            while (extra != 0 && temp2 != null) {  //上一位出现进位，需要加上
                temp2.val = temp2.val + extra;
                extra = 0;
                if (temp2.val > 9) {
                    extra = 1;
                }
                temp2.val %= 10;
                temp2 = temp2.next;
            }
            p.next = temp;
            if (temp2 == null && extra == 1) {  //判断最后一位是否还有进位并操作
                temp2 = new ListNode();
                temp2.val = 1;
                while (temp.next != null) temp = temp.next;
                temp.next=temp2;
            }

        }
        else if(temp2==null&&extra==1){  //两个数长度相同但最终产生进位进行的操作
            ListNode listNode = new ListNode();
            listNode.val=1;
            p.next=listNode;
        }
        return head.next;       //这里head存的是头节点，因此要返回next


    }
}