LeetCode 2：Add Two Numbers解题

终于，隔了很久之后，我又开始题了。 其实刷OJ是为了保研机试提前做准备，也是为了给自己的编程知识保温，但是当我发现自己两个月了还在刷easy难度的题目的时候，我知道，我得挑战点真正的题目了。

还是先来看一下今天的题目

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself. 举例

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8 Explanation: 342 + 465 = 807.

注意这里链表题目已经给你反向好了，做的时候直接从头开始处理就好了，并且输出的链表也是反向的，不用进行反向处理。

隔了这么久做题，手感冰凉，愣是刚了一上午，没弄出来2333，我的方法总是有个case过不了，无奈之下，去看了人家的算法，发现我之前的想法是真的土。

更好的算法

这是LeetCode上我写的时候排名第一的算法，简明扼要，惊为天人。 算法的妙处在于设置了一个全局变量carry，存储每次两个链表节点相加的和，用第三个链表保存其对10取模的值，然后将其除以10更新，这样就解决了进位的问题，最后只需要再判断当前carry是不是1（进位导致carry值剩下1）再新增一个节点即可。

sample 22 ms submission
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
static const auto _____ = []()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    return nullptr;
}();

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode *head = new ListNode(0);
        ListNode *tail = head;

        int carry = 0;
        while(l1 || l2 || carry){
            int n = (l1?l1->val:0) + (l2?l2->val:0) + carry;
            tail -> next = new ListNode(n % 10);
            carry = n / 10;
            tail = tail -> next;
            l1 = l1?l1 -> next:NULL;
            l2 = l2?l2 -> next:NULL;
        }
        return head -> next;
    }
};