2.两数相加

LeetCode LeetCode 热题100 数学 链表 递归
发布时间 :
字数:2.4k 阅读 : 评论:
  1. 2.两数相加
    1. 2.1 题目
    2. 2.2 题解
      1. 方法一：迭代法
        1. 思路
        2. 复杂度分析
        3. 代码
      2. 方法二：递归法
        1. 思路
        2. 复杂度分析
        3. 代码
      3. 打印链表方法
    3. 2.3 代码
    4. 2.4 运行结果

2.两数相加

2.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]

提示：

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

2.2 题解

方法一：迭代法

思路

这道题的本质就是模拟我们小学学的竖式加法。两个链表都是逆序存储的，也就是说链表头是个位，这反而方便了我们——从头开始遍历，正好就是从个位开始相加。

我们需要处理的核心问题有两个：

  1. 逐位相加：对应位置的数字相加，加上来自低位的进位
  2. 进位处理：如果某一位的和 ≥ 10，需要向高位进 1

具体实现时，用 carry 变量记录进位，每次计算 sum = l1.val + l2.val + carry，取个位作为当前位结果，十位作为新的进位。注意循环条件要包含 carry != 0，因为最后可能还有进位需要处理（比如 9+1=10，会多出一个节点）。

举个例子：l1 = [2,4,3]（表示342），l2 = [5,6,4]（表示465）

  • 第1位：2+5+0=7，无进位，结果 [7]
  • 第2位：4+6+0=10，进位1，结果 [7,0]
  • 第3位：3+4+1=8，无进位，结果 [7,0,8]
  • 最终结果 [7,0,8] 表示 807，正确！

复杂度分析

  • 时间复杂度：O(max(m, n))，遍历两个链表中较长的那个
  • 空间复杂度：O(max(m, n))，结果链表的长度

代码

// 方法一：迭代法
// 使用循环，逐步计算相加结果，并在遍历完整个链表后返回结果链表头。
static ListNode AddTwoNumbers1(ListNode l1, ListNode l2)
{
    // 创建一个新的链表头节点
    ListNode resultListHeadNode = new ListNode();

    // 创建一个当前节点指针，用于遍历结果链表
    ListNode currentNode = resultListHeadNode;

    // 进位值，用于处理相加结果大于等于10的情况
    int carryVal = 0;

    // 遍历输入的两个链表，或者处理进位值
    while (l1 != null || l2 != null || carryVal != 0)
    {
        // 获取当前节点的值，如果节点为null则默认值为0
        int l1Val = l1?.val ?? 0;
        int l2Val = l2?.val ?? 0;

        // 计算两个节点值以及进位的和
        int sumVal = l1Val + l2Val + carryVal;
        
        // 计算个位数的值
        int onesVal = sumVal % 10;
        
        // 更新进位值，如果和大于等于10则进位为1，否则为0
        carryVal = sumVal / 10;
        
        // 将当前节点的值设置为个位数的值
        currentNode.val = onesVal;

        // 移动到下一个节点
        if (l1 != null) l1 = l1.next;
        if (l2 != null) l2 = l2.next;

        // 如果仍有节点或者有进位值，创建一个新节点并将当前节点指针移动到新节点
        if (l1 != null || l2 != null || carryVal != 0)
        {
            currentNode.next = new ListNode();
            currentNode = currentNode.next;
        }
    }

    // 返回结果链表的头节点
    return resultListHeadNode;
}

方法二：递归法

思路

递归的思路和迭代完全一致，只是换了一种写法。每次递归处理当前位的相加，然后把剩余的工作交给下一层递归。

递归三要素：

  1. 终止条件：两个链表都遍历完，且没有进位
  2. 当前层逻辑：计算当前位的和，创建节点
  3. 递归调用：处理下一位

递归的好处是代码更简洁，但要注意递归深度不能太大（本题最多100层，没问题）。

复杂度分析

  • 时间复杂度：O(max(m, n))，递归深度为链表最大长度
  • 空间复杂度：O(max(m, n))，递归调用栈的空间

代码

// 方法二：递归法
// 终止条件是两表为空且无进位则返回空，处理当前节点，递归调用设置当前节点的下一节点
static ListNode AddTwoNumbers2(ListNode l1, ListNode l2)
{
    return AddTwoNumbersHelper(l1, l2, 0);
}


// 方法二递归辅助函数，用于将两个链表相加
static ListNode AddTwoNumbersHelper(ListNode l1, ListNode l2, int carry)
{
    // 如果两个链表都为空且没有进位，返回空
    if (l1 == null && l2 == null && carry == 0)
        return null;

    // 获取当前节点的值，如果节点为null则默认值为0
    int l1Val = l1?.val ?? 0;
    int l2Val = l2?.val ?? 0;

    // 计算两个节点值以及进位的和
    int sumVal = l1Val + l2Val + carry;
    // 计算个位数的值
    int onesVal = sumVal % 10;
    // 更新进位值，如果和大于等于10则进位为1，否则为0
    int carryVal = sumVal / 10;

    // 创建当前节点并递归处理下一个节点
    ListNode currentNode = new ListNode(onesVal);
    currentNode.next = AddTwoNumbersHelper(l1?.next, l2?.next, carryVal);

    return currentNode;
}

打印链表方法

// 打印链表方法
static void PrintList(ListNode head)
{
    while (head != null)
    {
        Console.Write(head.val + " ");
        head = head.next;
    }

    Console.WriteLine();
}

2.3 代码

using System;

public class ListNode
{
    public int val;
    public ListNode next;

    public ListNode(int val = 0, ListNode next = null)
    {
        this.val = val;
        this.next = next;
    }
}

class Program
{
    static void Main()
    {
        #region 题目

        // 给定两个非空的链表，它们分别表示两个非负整数。每个节点包含一个数字，且这些数字按逆序方式存储，也就是个位数排在链表的最前面。
        // 请你将这两个数相加，并以相同形式返回一个表示和的链表。
        // 你可以假设除了数字 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。
        // 题目数据保证列表表示的数字不含前导零。

        #endregion

        #region 测试

        // 示例 1
        ListNode l1 = new ListNode(2, new ListNode(4, new ListNode(3)));
        ListNode l2 = new ListNode(5, new ListNode(6, new ListNode(4)));
        ListNode result11 = AddTwoNumbers1(l1, l2);
        Console.Write("示例1 方法1 输出：");
        PrintList(result11);
        ListNode result12 = AddTwoNumbers2(l1, l2);
        Console.Write("示例1 方法2 输出：");
        PrintList(result12);

        // 示例 2
        ListNode l3 = new ListNode(0);
        ListNode l4 = new ListNode(0);
        ListNode result21 = AddTwoNumbers1(l3, l4);
        Console.Write("示例2 方法1 输出：");
        PrintList(result21);
        ListNode result22 = AddTwoNumbers2(l3, l4);
        Console.Write("示例2 方法2 输出：");
        PrintList(result22);

        // 示例 3
        ListNode l5 = new ListNode(9,
            new ListNode(9, new ListNode(9, new ListNode(9, new ListNode(9, new ListNode(9, new ListNode(9)))))));
        ListNode l6 = new ListNode(9, new ListNode(9, new ListNode(9, new ListNode(9))));
        ListNode result31 = AddTwoNumbers1(l5, l6);
        Console.Write("示例3 方法1 输出：");
        PrintList(result31);
        ListNode result32 = AddTwoNumbers2(l5, l6);
        Console.Write("示例3 方法2 输出：");
        PrintList(result32);

        #endregion
    }

    #region 答案

    // 方法一：迭代法
    // 使用循环，逐步计算相加结果，并在遍历完整个链表后返回结果链表头。
    static ListNode AddTwoNumbers1(ListNode l1, ListNode l2)
    {
        // 创建一个新的链表头节点
        ListNode resultListHeadNode = new ListNode();

        // 创建一个当前节点指针，用于遍历结果链表
        ListNode currentNode = resultListHeadNode;

        // 进位值，用于处理相加结果大于等于10的情况
        int carryVal = 0;

        // 遍历输入的两个链表，或者处理进位值
        while (l1 != null || l2 != null || carryVal != 0)
        {
            // 获取当前节点的值，如果节点为null则默认值为0
            int l1Val = l1?.val ?? 0;
            int l2Val = l2?.val ?? 0;

            // 计算两个节点值以及进位的和
            int sumVal = l1Val + l2Val + carryVal;
            
            // 计算个位数的值
            int onesVal = sumVal % 10;
            
            // 更新进位值，如果和大于等于10则进位为1，否则为0
            carryVal = sumVal / 10;
            
            // 将当前节点的值设置为个位数的值
            currentNode.val = onesVal;

            // 移动到下一个节点
            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;

            // 如果仍有节点或者有进位值，创建一个新节点并将当前节点指针移动到新节点
            if (l1 != null || l2 != null || carryVal != 0)
            {
                currentNode.next = new ListNode();
                currentNode = currentNode.next;
            }
        }

        // 返回结果链表的头节点
        return resultListHeadNode;
    }

    // 方法二：递归法
    // 终止条件是两表为空且无进位则返回空，处理当前节点，递归调用设置当前节点的下一节点
    static ListNode AddTwoNumbers2(ListNode l1, ListNode l2)
    {
        return AddTwoNumbersHelper(l1, l2, 0);
    }


    // 方法二递归辅助函数，用于将两个链表相加
    static ListNode AddTwoNumbersHelper(ListNode l1, ListNode l2, int carry)
    {
        // 如果两个链表都为空且没有进位，返回空
        if (l1 == null && l2 == null && carry == 0)
            return null;

        // 获取当前节点的值，如果节点为null则默认值为0
        int l1Val = l1?.val ?? 0;
        int l2Val = l2?.val ?? 0;

        // 计算两个节点值以及进位的和
        int sumVal = l1Val + l2Val + carry;
        // 计算个位数的值
        int onesVal = sumVal % 10;
        // 更新进位值，如果和大于等于10则进位为1，否则为0
        int carryVal = sumVal / 10;

        // 创建当前节点并递归处理下一个节点
        ListNode currentNode = new ListNode(onesVal);
        currentNode.next = AddTwoNumbersHelper(l1?.next, l2?.next, carryVal);

        return currentNode;
    }

    // 打印链表方法
    static void PrintList(ListNode head)
    {
        while (head != null)
        {
            Console.Write(head.val + " ");
            head = head.next;
        }

        Console.WriteLine();
    }

    #endregion
}

2.4 运行结果

示例1 方法1 输出：7 0 8 
示例1 方法2 输出：7 0 8 
示例2 方法1 输出：0 
示例2 方法2 输出：0 
示例3 方法1 输出：8 9 9 9 0 0 0 1 
示例3 方法2 输出：8 9 9 9 0 0
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com

赏

©2016-2026 Tao

Built with Hexo and 3-hexo theme

×

喜欢就点赞,疼爱就打赏