正文
两数相加（C#数据结构和算法练习）
小程序：扫一扫查出行【扫一扫了解最新限行尾号】
复制小程序
两数相加
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 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(); //当前节点，进行迭代
ListNode head = result; //头节点
int next = ; //若相加大于10进位则next==1
while (l1 != null || l2 != null)
{
int value1, value2;
if (l1 == null) //当l1或l2为空时，假设值为0
value1 = ;
else
value1 = l1.val;
if (l2 == null)
value2 = ;
else
value2 = l2.val;
int temp = value1 + value2;
result.val = temp + next;
if (result.val < ) //判断是否进位
{
next = ;
}
else
{
result.val = result.val - ;
next = ;
}
if (l1 != null) //l1和l2不为空时迭代
l1 = l1.next;
if (l2 != null)
l2 = l2.next;
if (l1 == null && l2 == null) //同时为空时结束，避免下方语句进行使得结果错误
break;
result.next = new ListNode();
result = result.next;
}
if (next == ) //出现进位但l1和l2下一数字都为0时上述循环无法进行，做特殊处理
{
result.next = new ListNode();
}
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(); //当前节点，进行迭代
ListNode head = result; //头节点
int next = ; //若相加大于10进位则next==1
while (l1 != null || l2 != null)
{
int value1, value2;
if (l1 == null) //当l1或l2为空时，假设值为0
value1 = ;
else
value1 = l1.val;
if (l2 == null)
value2 = ;
else
value2 = l2.val;
int temp = value1 + value2;
result.val = temp + next;
if (result.val < ) //判断是否进位
{
next = ;
}
else
{
result.val = result.val - ;
next = ;
}
if (l1 != null) //l1和l2不为空时迭代
l1 = l1.next;
if (l2 != null)
l2 = l2.next;
if (l1 == null && l2 == null) //同时为空时结束，避免下方语句进行使得结果错误
break;
result.next = new ListNode();
result = result.next;
}
if (next == ) //出现进位但l1和l2下一数字都为0时上述循环无法进行，做特殊处理
{
result.next = new ListNode();
}
return head;
}
static void Main(string[] args) //简单测试
{
ListNode l1 = new ListNode();
l1.next = new ListNode();
//l1.next.next = new ListNode(3); ListNode l2 = new ListNode();
//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] | 求和运算最后可能出现额外的进位，这一点很容易被遗忘 |
