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

    如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
    您可以假设除了数字 0 之外，这两个数都不会以 0 开头。 示例：
    输入：(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出：7 -> 0 -> 8 原因：342 + 465 = 807

    这是LeetCode上的第二题，难度是中等，老习惯，先看题干整理出函数头
    输入是两条非空链表。链表的数据结构LeetCode已经给出

    1. public class ListNode {
    2.     public int val;
    3.     public ListNode next;
    4.     public ListNode(int x) { val = x; }
    5. }

    输出是一条链表，那么很简单，我们的函数头即为

    1. public ListNode addTwoNumbers(ListNode l1, ListNode l2)

    咱们再看题目要我们做什么吧。链表是按照 逆序 方式存储了两个数字，并且每个节点只有一位数字，意思就是：1234会以 4->3->2->1的形式存储在链表中。
    然后将两条链表相加，返回一个同样形式的链表。

    那么，大家现在对这道题有什么想法吗？是不是想把这两个链表转化为两个Int然后进行相加。再逐位写入新的链表中，简单快捷。

    如果是这样，那么恭喜你，掉进陷阱了。
    为什么？因为题目并没有说这个链表是多少位的，它可能有很多位，多到所有数值类型都装不下。

    其实我很早就遇到过这道题目，这道题是我大学C++课程期末考试的最后一题。所以这次看到之后就直接想到了解法。其实这个解法的原理很简单，就是咱们小学学过的加法竖式
    temp.png
    看，有没有瞬间想到了怎么解呢？那么我们就开始一步步用程序来实现竖式的计算过程吧，首先我们先实现两条链表都只有一位的计算，就把9+7给实现以下吧

    1. ListNode l1 = new ListNode(7);
    2. ListNode l2 = new ListNode(9);
    4. int l1Val = l1.val;
    5. int l2Val = l2.val;
    6. int carry = 0;  //进位
    7. int temp = l1Val + l2Val + carry;  //上数 加 下数 加 进位
    8. carry = temp / 10;  //获得进位的数值
    9. int nodeVal = temp % 10; //获取个位的数值
    10. ListNode resNode = new ListNode(nodeVal); //这就是加后个位得出的值
    12. l1 = l1.next; l2 = l2.next;//移位，但是我们知道这两个都没有下一位了
    14. if (l1 != null || l2 != null || carry > 0)//判断有没有下一位
    15. {
    16.     l1Val = l1 == null ? 0 : l1.val; //判断l1链表十位是否为空
    17.     l2Val = l2 == null ? 0 : l2.val; //判断l2链表十位是否为空
    19.     temp = l1Val + l2Val + carry;
    20.     resNode.next = new ListNode(temp);//这里我们知道它不会有下一位了
    21. }
    22. return resNode;

    是不是完全就是小学生的思维模式啊，很简单对不对？
    现在只需要将之转化为while 循环即可。这里我们能看出判断是否能继续进行的条件为
    if (l1 != null || l2 != null || carry > 0)
    那么具体的函数我们就可以构建成

    1. public ListNode AddTwoNumbers(ListNode l1, ListNode l2)
    2. {
    3.     ListNode resNode = new ListNode(-1);//链表头节点，输出的时候这个节点不要
    4.     ListNode currNode = resNode; //当前使用的节点
    5.     int carry = 0;//进位
    6.     int l1Val;  //上数
    7.     int l2Val;  //下数
    8.     int temp;
    9.     while (l1 != null || l2 != null || carry > 0)
    10.     {
    11.         l1Val = l1 == null ? 0 : l1.val;
    12.         l2Val = l2 == null ? 0 : l2.val;
    14.         temp = l1Val + l2Val + carry;  //上数 加 下数 加 进位
    15.         carry = temp / 10;  //获得进位的数值
    17.         currNode.next = new ListNode(temp % 10);//把当前位的值写入链表
    18.         currNode = currNode.next;
    20.         l1 = l1 == null ? null : l1.next;
    21.         l2 = l2 == null ? null : l2.next;//移位，但是我们知道这两个都没有下一位了
    22.     }
    23.     return resNode.next;
    24. }

    放入LeetCode跑一下
    执行用时 :116 ms, 在所有 C# 提交中击败了99.18%的用户
    内存消耗 :26.8 MB, 在所有 C# 提交中击败了5.07%的用户
    结果还不错。这个算法的时间复杂度是一层循环，次数根据 l1 和 l2 的长度最大值相关 即为 O(max(m,n))
    空间上，为结果链表长度 即 l1 和 l2 的长度最大值（+1 可能进位） 即 max(m,n)+1