LeetCode刷题之路第二题两数相加

2021年6月21日15:56:31算法 LeetCode评论106阅读模式

题目链接

https://leetcode-cn.com/problems/add-two-numbers/文章源自随机的未知-https://sjdwz.com/11148.html

题目描述

给你两个非空的链表,表示两个非负的整数。它们每位数字都是按照逆序的方式存储的,并且每个节点只能存储一位数字。
请你将两个数相加,并以相同形式返回一个表示和的链表。
你可以假设除了数字0之外,这两个数都不会以0开头。文章源自随机的未知-https://sjdwz.com/11148.html

示例如下:文章源自随机的未知-https://sjdwz.com/11148.html

输入:l1 = [2,4,3], l2 = [5,6,4]
输出:[7,0,8]
解释:342 + 465 = 807.文章源自随机的未知-https://sjdwz.com/11148.html

LeetCode刷题之路第二题两数相加文章源自随机的未知-https://sjdwz.com/11148.html

分析

1.参数是两个链表,两个链表可能包含空链表,可能两个链表长度不同,我们应该将较长的链表遍历完,才能得到最终结果;当长链表没有遍历完,短链表遍历完时,应该补0相加;
2.当两个数字相加之后,我们应该考虑进位,再将进位加到下面两个数相加的和中;
3.返回结果是链表节点,所以我们需要定义一个链表节点,为了方便操作,我们可以建立一个虚拟节点,指向真正的和节点,用来方便操作;文章源自随机的未知-https://sjdwz.com/11148.html

代码和解释

1.首先要初始化虚拟节点,和节点,进位数字:文章源自随机的未知-https://sjdwz.com/11148.html

ListNode preNode = new ListNode(0);         
ListNode currentNode = preNode;           
int carry = 0;     

2.进入循环,进入循环的条件为,两个链表有一个不为空:
即:文章源自随机的未知-https://sjdwz.com/11148.html

while(l1 != null || l2 != null)                  

循环内部:
需要有两个数字保存两个链表对应的数值:文章源自随机的未知-https://sjdwz.com/11148.html

int num1 = l1==null?0:l1.val;       
int num2 = l2==null?0:l2.val;

计算和(可能超过10):文章源自随机的未知-https://sjdwz.com/11148.html

int sum = num1 + num2 + carry;                

计算进位数值和sum余10结果:文章源自随机的未知-https://sjdwz.com/11148.html

carry = sum / 10;            
sum = sum % 10;                

然后建立新节点,让当前节点后移;文章源自随机的未知-https://sjdwz.com/11148.html

currentNode.next = new ListNode(sum);                    
currentNode = currentNode.next;     

判断两个链表是否为空,如果不为空,向后移动;文章源自随机的未知-https://sjdwz.com/11148.html

 if(l1 != null)      
    l1 = l1.next;      
 if(l2 != null)        
    l2 = l2.next;

3.退出循环后,看进位是否为0,如果不为0,再新建节点:文章源自随机的未知-https://sjdwz.com/11148.html

if(carry == 1){
  currentNode.next = new ListNode(1);
}

完整代码如下:文章源自随机的未知-https://sjdwz.com/11148.html

/**
 * @user: code随笔
 */
public class Solution {

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

        ListNode preNode = new ListNode(0);
        ListNode currentNode = preNode;
        int carry = 0;

        while(l1 != null || l2 != null){

            int num1 = l1==null?0:l1.val;
            int num2 = l2==null?0:l2.val;

            int sum = num1 + num2 + carry;

            carry = sum / 10;
            sum = sum % 10;

            currentNode.next = new ListNode(sum);
            currentNode = currentNode.next;

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

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

        }

        if(carry == 1){
            currentNode.next = new ListNode(1);
        }

        return preNode.next;
    }
}

微信搜索:随机的未知 欢迎关注乐于输出Java,算法等干货的技术公众号。文章源自随机的未知-https://sjdwz.com/11148.html

文章源自随机的未知-https://sjdwz.com/11148.html
欢迎关注本站微信公众号:随机的未知 如果喜欢本文,欢迎点赞,收藏,转发,打赏。
  • 本文由 发表于 2021年6月21日15:56:31
  • 转载请注明:来源:随机的未知 本文链接https://sjdwz.com/11148.html
算法

详解堆排序

什么是堆 堆首先是一个完全二叉树,堆分为大顶堆和小顶堆; 大顶堆 : 每个节点的值大于或等于其左右孩子节点的值,称为大顶堆。 小顶堆同理就是每个节点的值小于或等于其左右孩子节点的值。 注意: 每个节点...
算法

详解基数排序

基本思想 基数排序的思想是将整数按位数切割成不同的数字,然后按每个位数分别比较从而得到有序的序列。 例子 本文以数组中元素均为正整数来演示思想。 给定一个数组 arr = < 6, 56, 89 , ...
算法

详解归并排序

基本思想 归并排序的基本思想是: 先将序列一次次分成子序列,直到子序列长度为1; 再将已有序的子序列合并,得到完全有序的序列。 可以看出归并排序运用了 分而治之的思想 。 例子 输入数组 < 2, 5...
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定