题目连接：2.两数相加
题意题目难度标为 中等, 因为题意上有一部分理解难度，以及需要数据结构的链表基础。
还不知道到链表的童鞋可以粗略的看下百度百科或者是翻出数据结构的书看一看，通俗一点的语言来解释链表就是：上线和下线。
上线知道自己的下线，但不知道自己下线的下线，同时也不知道自己的上线是谁。
这就是单向链表。
这道题的题意就是将两个数字变成了两个单向链表，其中每一个节点存储一位数字，且是逆序存放，也就是倒过来存了。
解题思路首先来想一下不同情况和对应的案例：
两个链表长度相等。
输入：(2 -> 4 -> 3) + (5 ->6 -> 4)
输出：(7 -> 0 -> 8)
两个链表长度不等。
输入：(2 -> 4) + (5 -> 6 -> 4)
输出：(7 -> 0 -> 5)
最终结果的最高位存在进位的情况。
输入：(2 -> 4 -> 5) + (5 -> 6 -> 4)
输出：(7 -> 0 -> 0 -> 1)
解题的关键便是：合并链表并且保证进位正确。
模拟进位首先我们按位相加，然后再对每一位进行进位处理，满 10 则进 1。
代码：
public class Solution { public ListNode AddTwoNumbers(ListNode l1, ListNode l2) { ListNode first = null; ListNode current = null; IList<int> sums = new List<int>(); int sum = 0; int res = 0; while (l1 != null || l2 != null) { sum = res; if (l1 != null) { sum += l1.val; l1 = l1.next; } if (l2 != null) { sum += l2.val; l2 = l2.next; } res = sum / 10; sum %= 10; sums.Add(sum); } if(res > 0) sums.Add(res); if(sums.Any()) first = new ListNode(sums[0]); current = first; for (int i = 1; i < sums.Count; i++) { current.next = new ListNode(sums[i]); current = current.next; } return first; } }执行用时: 252 ms, 在所有 C# 提交中击败了13.33%的用户
内存消耗: 26.7 MB
这个耗时有点凄惨，接近垫底了。那也说明了还有很大的优化空间。
优化常量上面我们在循环时使用到了 IList 的 Count，这里我们可以提前将其存储起来。
代码如下：
public class Solution { public ListNode AddTwoNumbers(ListNode l1, ListNode l2) { ListNode first = null; ListNode current = null; IList<int> sums = new List<int>(); int sum = 0; int res = 0; int count = 0; while (l1 != null || l2 != null) { sum = res; if (l1 != null) { sum += l1.val; l1 = l1.next; } if (l2 != null) { sum += l2.val; l2 = l2.next; } res = sum / 10; sum %= 10; sums.Add(sum); } if (res > 0) sums.Add(res); count = sums.Count; if (count > 0) first = new ListNode(sums[0]); current = first; for (int i = 1; i < count; i++) { current.next = new ListNode(sums[i]); current = current.next; } return first; } }执行用时: 164 ms, 在所有 C# 提交中击败了85.62%的用户
内存消耗: 26.8 MB
仅仅是替换了一个变量，执行用时就优化了近 100ms！ 这 100ms 就超过了 70% 的提交。
前面还有近 15% 说明还有优化空间。
优化循环数上面的算法，如果按照大O表示法来计算复杂度的话，它的复杂度是：O(max(l1.Length, l2.Length)) ，再精简一下也就是 O(n)，即单重循环的程度。
但真正的复杂度是（同样也是估算，循环内的操作数没有算进来，这里只算了循环的）：2 * max(l1.Length, l2.Length) + 1。因为这里实际上是使用了两个循环。那么我们可以将这个复杂度表达式中的倍数 : 2 去掉，即只用一重循环。
代码如下：
public class Solution { public ListNode AddTwoNumbers(ListNode l1, ListNode l2) { ListNode first = null; ListNode current = null; int sum = 0; int res = 0; while (l1 != null || l2 != null) { sum = res; if (l1 != null) { sum += l1.val; l1 = l1.next; } if (l2 != null) { sum += l2.val; l2 = l2.next; } res = sum / 10; sum %= 10; if (current == null) { first = new ListNode(sum); current = first; } else { current.next = new ListNode(sum); current = current.next; } } if (res > 0) current.next = new ListNode(res); return first; } }执行用时: 136 ms, 在所有 C# 提交中击败了98.85%的用户
内存消耗: 26.5 MB
在我们移除掉一重循环之后，执行用时优化了 20 多ms(为什么不是优化了近一半的时间？)，而这 20 多ms就又超过了 13% 的提交。
对于Leetcode判题耗时的思考处于对连续两道题目都没有办法达到最优（至少前 1% ）的情况下，若羽今天写到这里时，特意去看了一下耗时最短的代码（104ms），复制下来之后直接提交，结果显示是 248ms !??
再次提交之后结果显示是 160 ms !??