【原】【小Y学算法】⚡️每日LeetCode打卡⚡️——2.两数相加

敲代码的小Y 2021-12-01

展开全文

📢前言

🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻
🌲 每天打卡一道算法题，既是一个学习过程，又是一个分享的过程😜
🌲 提示：本专栏解题编程语言一律使用 C# 和 Java 两种进行解题
🌲 要保持一个每天都在学习的状态，让我们一起努力成为算法大神吧🧐！
🌲 今天是力扣算法题持续打卡第2天🎈！
🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻

🌲原题样例

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

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

你可以假设除了数字 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
题目数据保证列表表示的数字不含前导零

🌞解题思路

🌻 C#方法

核心思路就是do while循环两张链表，将他们每一位的值加起来，如果存在进位的话就将进位存在Other变量中下一次循环使用。在下一次循环时Ohter又会被重置。

代码

    public static ListNode AddTwoNumbers(ListNode l1, ListNode l2)
            //定义返回值
            var result = new ListNode(-1);
            //定义循环用的对象，将形参制定到temp
            var temp = result;
            //前一轮数字和的十位数
            int Other = 0;
            do
            {
                //取出numbe1和number2的值
                var number1 = l1 == null ? 0 : l1.val;
                var number2 = l2 == null ? 0 : l2.val;
                //计算两数之和 并加上前一轮需要进位的值
                var sum = number1 + number2 + Other;
                //计算个位
                var value = sum % 10 ;
                //计算十位并赋值
                Other = sum / 10;
                //将数据添加到循环链表中
                temp.next = new ListNode(value);
                //循环用的temp对象赋值为循环链表中的下一个对象
                temp = temp.next;
                //l1 l2 指向自己在链表中对应的下一个值
                l1 = l1?.next;
                l2 = l2?.next;
            } while (l1 != null || l2 != null|| Other!=0);
            return result.next;
        }

执行结果

执行结果通过，执行用时116ms，内存消耗 27.7 MB.

🎋Java方法：模拟

思路与算法

由于输入的两个链表都是逆序存储数字的位数的，因此两个链表中同一位置的数字可以直接相加。

我们同时遍历两个链表，逐位计算它们的和，并与当前位置的进位值相加。具体而言，如果当前两个链表处相应位置的数字为 n1,n2n1,n2，进位值为 \textit{carry}carry，则它们的和为 n1+n2+\textit{carry}n1+n2+carry；

其中，答案链表处相应位置的数字为 (n1+n2+\textit{carry}) \bmod 10(n1+n2+carry)mod10，而新的进位值为 \lfloor\frac{n1+n2+\textit{carry}}{10}\rfloor⌊ 10n1+n2+carry ⌋。

如果两个链表的长度不同，则可以认为长度短的链表的后面有若干个 00 。

此外，如果链表遍历结束后，有 \textit{carry} > 0carry>0，还需要在答案链表的后面附加一个节点，节点的值为 \textit{carry}carry。

代码

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = null, tail = null;
        int carry = 0;
        while (l1 != null || l2 != null) {
            int n1 = l1 != null ? l1.val : 0;
            int n2 = l2 != null ? l2.val : 0;
            int sum = n1 + n2 + carry;
            if (head == null) {
                head = tail = new ListNode(sum % 10);
            } else {
                tail.next = new ListNode(sum % 10);
                tail = tail.next;
            }
            carry = sum / 10;
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }
        if (carry > 0) {
            tail.next = new ListNode(carry);
        }
        return head;
    }
}