LeetCode(C++)刷题计划：2-两数相加

2-两数相加

@Author：CSU张扬
@Email：csuzhangyang@gmail.com or csuzhangyang@qq.com

1. 题目

给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-two-numbers

2. 解法

2.1 解法一

例如
(2 -> 4 -> 3) +
(5 -> 6 -> 4 -> 2)
新建一个链表h，用于存储每一步相加的结果。
首先循环内的条件为l1 || l2，即l1或l2有一个不为空时。
对于l1和l2，如果没有到达尾部，则链表指向下一个（next），并且sum加上其值；如果某链表到达尾部之后（即为NULL时），链表则不动，也不再加上该链表的值。
将对应位置两个数相加，如果>=10，进位标志(carry)为true。此时下一次循环的sum要额外加1。
循环结束后，如果最后两个数字相加>=10（即carry==true），则还要增加一个节点，值为1。
注意：我们并没有使用h的头结点，我们先是令其指向next，再赋值。主要是考虑最后一次循环，不这样的话会创建一个新的无用的节点。
最后我们释放掉无用的头结点，因为如果调用次数多会溢出。

执行用时：28 ms, 在所有 cpp 提交中击败了91.26%的用户
内存消耗：10.3 MB, 在所有 cpp 提交中击败了84.73%的用户

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode *head = new ListNode(-1); //头结点，不保存任何信息
        ListNode *h = head;
        int sum;
        bool carry = false;
        while (l1 || l2) {
            sum = 0;
            if (l1) {
                sum += l1->val;
                l1 = l1->next;
            }   
            if (l2) {
                sum += l2->val;
                l2 = l2->next;
            }  
            if (carry)
                sum ++;
            carry = (sum >= 10 ? true : false);
            head->next = new ListNode(0);
            head = head->next;
            head->val = sum % 10;
        }
        if (carry)
            head->next = new ListNode(1);
        // 释放头结点（初始创建的val = -1 的节点），c++要手动释放，否则调用次数多会溢出
        ListNode *ptrDelete = h;
        h = h->next;
        delete ptrDelete;
        return h;
        // 参考https://leetcode-cn.com/u/chenlele/
    }
};