Loading...
墨滴

Kisrain

2021/09/06  阅读:43  主题:默认主题

leecode

Leecode 两数相加

题目描述

给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。请你将两个数相加,并以相同形式返回一个表示和的链表。你可以假设除了数字 0 之外,这两个数都不会以 0 开头

示例 1:

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

示例 2:

输入:nums = [3,2,4], target = 6 输出:[1,2]

示例 3:

输入:l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] 输出:[8,9,9,9,0,0,0,1] 解释:9999999+9999=10009998

题解

  1. 首先搞明白题目的意思,其实就是把数字倒过来,然后每一位用链表的一个节点存储。比如342,倒过来就是243,然后每一位用节点存储,就是图片所示内容。因为加法操作是从低位到高位顺序相加,而链表存储的正好是低位到高位,因此直接从前往后对齐链表做加法就可以。

  2. 需要注意的就是两个链表对应位置相加之和超过10就要进一。另外就是最后一位点结果大于10也要进一位,可以单独处理。

  3. 拆解代码

int sum = 0;//表示两个链表对应位置相加之和

int flag = 0;//表示进位(如果sum值大于10,就需要进位,flag=1,否则不进位 flag=0)

            temp1 = l1.val; //第一个链表节点点值
            temp2 = l2.val; //第二个链表节点值
            sum = temp1+temp2+flag; //两者相加,再加上前一位的进位
            if(sum>=10){
                sum = sum-10;
                flag = 1;
            }else{
                flag = 0;
            }

完整代码

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int sum = 0;
        int flag = 0;
        ListNode res = new ListNode(0);
        ListNode temp = res;
        int temp1 = 0;
        int temp2 = 0;
        while(l1!=null&&l2!=null){
            temp1 = l1.val;
            temp2 = l2.val;
            sum = temp1+temp2+flag;
            if(sum>=10){
                sum = sum-10;
                flag = 1;
            }else{
                flag = 0;
            }
            res.next = new ListNode(sum);
            res = res.next;
            l1 = l1.next;
            l2 = l2.next;
        }
        while(l1!=null){
            temp1 = l1.val;
            sum = temp1+flag;
            if(sum>=10){
                sum = sum-10;
                flag = 1;
            }else{
                flag = 0;
            }
            res.next = new ListNode(sum);
            res = res.next;
            l1 = l1.next;
        }
        while(l2!=null){
            temp1 = l2.val;
            sum = temp1+flag;
            if(sum>=10){
                sum = sum-10;
                flag = 1;
            }else{
                flag = 0;
            }
            res.next = new ListNode(sum);
            res = res.next;
            l1 = l2.next;
        }
        if(flag==1){    //由于最后一位相加的结果可能大于10,所以还需要这一步的处理
            res.next = new ListNode(flag);
        }
        return temp.next;

    }
}

Kisrain

2021/09/06  阅读:43  主题:默认主题

作者介绍

Kisrain