两数相加(C#数据结构和算法练习)

C# 小时候可胖了 21℃ 0评论

两数相加

给出两个?非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照?逆序?的方式存储的,并且它们的每个节点只能存储?一位?数字。

如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。

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

示例:

输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 0 -> 8
原因:342 + 465 = 807

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/add-two-numbers
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

算法思路和官方相同,但就语句而言或许可以进一步优化
关键代码:

            ListNode result= new ListNode(0);      //当前节点,进行迭代
            ListNode head = result;                //头节点
            int next = 0;                          //若相加大于10进位则next==1
            while (l1 != null || l2 != null)
            {
                int value1, value2;
                if (l1 == null)                   //当l1或l2为空时,假设值为0
                    value1 = 0;
                else
                    value1 = l1.val;
                if (l2 == null)
                    value2 = 0;
                else
                    value2 = l2.val;
                int temp = value1 + value2;
                result.val = temp + next;
                if (result.val < 10)             //判断是否进位
                {
                    next = 0;
                }
                else
                {
                    result.val = result.val - 10;
                    next = 1;
                }
                if (l1 != null)                   //l1和l2不为空时迭代
                    l1 = l1.next;
                if (l2 != null)
                    l2 = l2.next;
                if (l1 == null && l2 == null)     //同时为空时结束,避免下方语句进行使得结果错误
                    break;
                result.next = new ListNode(0);
                result = result.next;
            }
            if (next == 1)                        //出现进位但l1和l2下一数字都为0时上述循环无法进行,做特殊处理
            {
                result.next = new ListNode(1);
            }
            return head;

?

完整代码:

using System;
namespace numAdd
{
    public class ListNode
    {
    public int val;
    public ListNode next;
    public ListNode(int x) { val = x; }
    }
    class Program
    {
        public static ListNode AddTwonumbers(ListNode l1, ListNode l2)
        {
            ListNode result= new ListNode(0);      //当前节点,进行迭代
            ListNode head = result;                //头节点
            int next = 0;                          //若相加大于10进位则next==1
            while (l1 != null || l2 != null)
            {
                int value1, value2;
                if (l1 == null)                   //当l1或l2为空时,假设值为0
                    value1 = 0;
                else
                    value1 = l1.val;
                if (l2 == null)
                    value2 = 0;
                else
                    value2 = l2.val;
                int temp = value1 + value2;
                result.val = temp + next;
                if (result.val < 10)             //判断是否进位
                {
                    next = 0;
                }
                else
                {
                    result.val = result.val - 10;
                    next = 1;
                }
                if (l1 != null)                   //l1和l2不为空时迭代
                    l1 = l1.next;
                if (l2 != null)
                    l2 = l2.next;
                if (l1 == null && l2 == null)     //同时为空时结束,避免下方语句进行使得结果错误
                    break;
                result.next = new ListNode(0);
                result = result.next;
            }
            if (next == 1)                        //出现进位但l1和l2下一数字都为0时上述循环无法进行,做特殊处理
            {
                result.next = new ListNode(1);
            }
            return head;
        }
        static void Main(string[] args)          //简单测试
        {
            ListNode l1 = new ListNode(9);
            l1.next = new ListNode(9);
            //l1.next.next = new ListNode(3);

            ListNode l2 = new ListNode(1);
            //l1.next = new ListNode(6);
            //l1.next.next = new ListNode(4);

            ListNode l3 = AddTwonumbers(l1, l2);
            while (l3 != null)
            {
                Console.WriteLine(l3.val);
                l3 = l3.next;
            }
        }
    }
}

算法

从最低一位开始相加,大于9则进位处理,直至到最后处理完成

以下特别情况要特别注意:

测试用例 说明
l1=[0,1],l2=[0,1,2]l2=[0,1,2] 当一个列表比另一个列表长时
l1=[],l2=[0,1]l2=[0,1] 当一个列表为空时,即出现空列表
l1=[9,9],l2=[1]l2=[1] 求和运算最后可能出现额外的进位,这一点很容易被遗忘

转载请注明:九层楼 » 两数相加(C#数据结构和算法练习)

喜欢 (0)
发表我的评论
取消评论
表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址