Leetcode 2. 链表中两数相加

Offer 驾到，掘友接招！我正在参与2022春招打卡活动，点击查看活动详情。

1、题目📑

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

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

你可以假设除了数字 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]

限制：

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

2、思路🧠

方法一：数学解法之进位问题

特判：
- 如果 l1 == null && l2 == null 则返回空
- 如果 l1 == null 则返回链表2
- 如果 l2 == null 则返回链表1
初始化：定义 ListNode result 链表的头部 值为0的头结点；定义 ListNode resultCur 指向链表 result 的头部 head
循环判断：l1 != null || l2 != null || carry != 0 所有条件都不满足时，退出循环。
- l1Val l2Val 如果链表为空则用0来代替该位的值
- sum 求出当前两个链表的加和，注意这里会有进位的操作，需要将进位的结果加进来
- carry = sum / 10 求出下一位的进位数字，并保存到下一位时进行加和
- ListNode t = new ListNode(sum % 10) 将当前位置的数字变为 存储一位数字
- resultCur.next = t resultCur = resultCur.next 将当前位置的数字加入到之前定义的新链表中，继续后移
- 同时，将不为空的链表节点也进行后移操作
返回 result 的下一个节点即可。

方法二：利用栈来解决求和

观察到从左到右依次是个-十-百-千，从个位开始算，方法类似于方法一

方法三：递归求和

观察到每次进行运算的是两个节点的值，还有进位的值进行加法运算，不妨定义一个函数，进行两两递归求和。

特判：
- 如果 l1 == null && l2 == null && carryNum 则返回空，递归结束条件
分情况考虑
- 如果链表2为空，将链表1的值加进位值在对其取余就是该链表节点的值，链表后移
- 如果链表1为空，将链表2的值加进位值在对其取余就是该链表节点的值，链表后移
开始递归，将下一个需要计算的两个链表的节点以及进位制放入方法内，进行递归运算。
返回头结点即可完成求和操作。

废话少说~~~~~上代码！

3、代码👨‍💻

第一次commit AC

/**
 * 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) {
        if(l1 == null && l2 == null) return null;
        if(l1 == null) return l2;
        if(l2 == null) return l1;
        ListNode result = new ListNode(0);
        ListNode resultCur = result;
        int carry = 0; // 是否进位
        while(l1 != null || l2 != null || carry != 0) {
            int l1Val = l1 == null ? 0 : l1.val;
            int l2Val = l2 == null ? 0 : l2.val;
            int sum = l1Val + l2Val + carry;
            carry = sum / 10;//进位

            ListNode t = new ListNode(sum % 10);
            
            resultCur.next = t;
            resultCur = resultCur.next;

            if(l1 != null) l1 = l1.next;
            if(l2 != null) l2 = l2.next;
        }
        return result.next;
    }
}

// 9999999
// 0009999
// 10009998

时间复杂度：O( max(M, N) ) 其中 M 和 N 分别为两个链表的长度。

空间复杂度：O( max(M, N) )

第二次commit AC

/**
 * 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) {
        if(l1 == null && l2 == null) return null;
        if(l1 == null) return l2;
        if(l2 == null) return l1;
        ListNode result = new ListNode(0);
        ListNode resultCur = result;
        Stack<Integer> s1 = new Stack<>();
        Stack<Integer> s2 = new Stack<>();
        int carry = 0; // 是否进位
        while(l1 != null || l2 != null || carry != 0) {
            s1.push(l1 == null ? 0 : l1.val);
            s2.push(l2 == null ? 0 : l2.val);
            int sum = s1.pop() + s2.pop() + carry;
            carry = sum / 10;//进位

            ListNode t = new ListNode(sum % 10);
            resultCur.next = t;

            resultCur = resultCur.next;

            if(l1 != null) l1 = l1.next;
            if(l2 != null) l2 = l2.next;
        }
        return result.next;
    }
}

// 9999999
// 0009999
// 10009998

时间复杂度：O( max(M, N) ) 其中 M 和 N 分别为两个链表的长度。

空间复杂度：O( max(M, N) )

第三次commit AC

/**
 * 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) {
        return add(l1, l2, 0);
    }

    public ListNode add(ListNode l1, ListNode l2,int carryNum) {
        if(l1 == null && l2 == null && carryNum == 0) return null;
        
        int carry = carryNum;
        if(l1 != null) {
            carry += l1.val;
            l1 = l1.next;
        }

        if(l2 != null) {
            carry += l2.val;
            l2 = l2.next;
        }

        ListNode node = new ListNode(carry % 10);
        node.next = add(l1, l2, carry / 10);
        return node;
    }
}

时间复杂度：O( max(M, N) ) 其中 M 和 N 分别为两个链表的长度。

空间复杂度：O( max(M, N) )

4、总结

该题目考察多个知识点递归、数学的概念，最大难度在于是否理解链表的结构，对于一位数字相加存在进位的问题，在进位的时候特别容易忽视，从而导致计算结果的失败。

5、链表的相关操作

链接直达🔗

剑指 Offer 18. 删除链表的节点 - 掘金

Leetcode 21. 合并两个有序链表 - 掘金

剑指 Offer 22. 链表中倒数第k个节点 - 掘金

剑指 Offer 24. 反转链表 - 掘金

❤️‍来自专栏《LeetCode基础算法题》欢迎订阅❤️‍

厂长写博客目的初衷很简单，希望大家在学习的过程中少走弯路，多学一些东西，对自己有帮助的留下你的赞赞👍或者关注➕都是对我最大的支持，你的关注和点赞给厂长每天更文的动力。

对文章其中一部分不理解，都可以评论区回复我，我们来一起讨论，共同学习，一起进步！

原题链接：2. 两数相加 - 力扣（LeetCode） (leetcode-cn.com)