前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >☆打卡算法☆LeetCode 2、两数相加 算法解析

☆打卡算法☆LeetCode 2、两数相加 算法解析

作者头像
恬静的小魔龙
发布2022-08-07 09:46:53
1420
发布2022-08-07 09:46:53
举报
文章被收录于专栏:Unity3D
大家好,我是小魔龙,Unity3D软件工程师,VR、AR,虚拟仿真方向,不定时更新软件开发技巧。

一、题目

1、算法题目

“将两个链表中的数字组合成两个数,两个数相加,并返回一个相同格式的表示和的链表。”

题目链接: 来源:力扣(LeetCode)

链接:https://leetcode-cn.com/problems/add-two-numbers/

2、题目描述

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

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

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

比如:

l1 = [1,2,3],l2 = [4,5,6] 输出:[9,7,5] 因为321 + 654 = 975 ,返回 [9,7,5] 。

二、解题

1、思路分析

这道题是算两个链表组成的数的和,所以首先在较短的链表后面补零让两个链表的位数补齐,再将链表中的元素相加,还要考虑进位问题。

2、代码实现

假设当前两个链表处相应位置的数字为n1,n2,进位值为carry,则它们的和为newVal=n1+n2+carry;

那么答案链表新的进位值为(n1 + n2 + carry) / 10 也就是 carry = newVal / 10; 那么答案链表的对应位置的数字为n1 + n2 + carry % 10 也就是 newVal %= 10;

代码语言:javascript
复制
public class Solution 
{
    public ListNode AddTwoNumbers(ListNode l1, ListNode l2) 
    {
        ListNode p1 = l1, p2 = l2;
        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;
        int carry = 0, newVal = 0;
        while (p1 != null || p2 != null || carry > 0) 
        {
            newVal = (p1 == null ? 0: p1.val) + (p2 == null ? 0: p2.val) + carry; 
            carry = newVal / 10;
            newVal %= 10;
            p.next = new ListNode(newVal);
            p1 = p1 == null? null: p1.next;
            p2 = p2 == null? null: p2.next;
            p = p.next;
        }
        return dummy.next;
    }
}           

执行结果:

image.png
image.png

3、时间复杂度

时间复杂度:O(max(m,n))

m和n是两个链表的长度。要遍历两个链表的全部位置,而每个位置只需要O(1)的时间。

空间复杂度:O(1)

三、总结

这道题难度中等,对于新学习算法的人来说还是有点难度的。

按顺序刷题的在默哀。。

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2021-09-26,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 一、题目
    • 1、算法题目
      • 2、题目描述
      • 二、解题
        • 1、思路分析
          • 2、代码实现
            • 3、时间复杂度
            • 三、总结
            领券
            问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档