2.两数相加

LeetCode LeetCode 数学 链表 递归
发布时间 :
字数:1.9k 阅读 : 评论:
  1. 2.两数相加
    1. 2.1 题目
    2. 2.2 题解
      1. 迭代法
      2. 递归法
      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 题解

迭代法

// 方法一：迭代法
// 使用循环，逐步计算相加结果，并在遍历完整个链表后返回结果链表头。
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();
}

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-2024 Tao

Built with Hexo and 3-hexo theme

×

喜欢就点赞,疼爱就打赏