题目描述：
    给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
    你可以假设除了数字 0 之外，这两个数字都不会以零开头。

    示例1：
    445. 两数相加 II - 图1
    输入：l1 = [7,2,4,3], l2 = [5,6,4] 输出：[7,8,0,7]
    示例2：
    输入：l1 = [2,4,3], l2 = [5,6,4] 输出：[8,0,7]
    示例3：
    输入：l1 = [0], l2 = [0] 输出：[0]

    提示：

    • 链表的长度范围为 [1, 100]
    • 0 <= node.val <= 9
    • 输入数据保证链表代表的数字无前导 0

    进阶：如果输入链表不能修改该如何处理？换句话说，不能对列表中的节点进行翻转。

    解题：

    1. /**
    2.  * Definition for singly-linked list.
    3.  * struct ListNode {
    4.  *     int val;
    5.  *     ListNode *next;
    6.  *     ListNode() : val(0), next(nullptr) {}
    7.  *     ListNode(int x) : val(x), next(nullptr) {}
    8.  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
    9.  * };
    10.  */
    11. class Solution {
    12. public:
    13.     ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    14.         ListNode* rList1 = reverseList(l1);
    15.         ListNode* rList2 = reverseList(l2);
    17.         ListNode headNode(0);
    18.         ListNode* pSumList = &headNode;
    19.         ListNode* pCur1 = rList1, *pCur2 = rList2;
    20.         int carry = 0;
    21.         while (pCur1 && pCur2) {
    22.             int sum = pCur1->val + pCur2->val + carry;
    23.             pSumList->next = new ListNode(sum % 10);
    24.             carry = sum / 10;
    25.             pSumList = pSumList->next;
    26.             pCur1 = pCur1->next;
    27.             pCur2 = pCur2->next;
    28.         }
    30.         while (pCur1) {
    31.             int sum = pCur1->val + carry;
    32.             pSumList->next = new ListNode(sum % 10);
    33.             carry = sum / 10;
    34.             pSumList = pSumList->next;
    35.             pCur1 = pCur1->next;
    36.         }
    38.         while (pCur2) {
    39.             int sum = pCur2->val + carry;
    40.             pSumList->next = new ListNode(sum % 10);
    41.             carry = sum / 10;
    42.             pSumList = pSumList->next;
    43.             pCur2 = pCur2->next;
    44.         }
    46.         if (carry != 0) {
    47.             pSumList->next = new ListNode(carry);
    48.             pSumList = pSumList->next;
    49.         }
    51.         pSumList->next = nullptr;
    52.         return reverseList(headNode.next);
    53.     }
    55.     ListNode* reverseList(ListNode* head) {
    56.         ListNode* cur = head;
    57.         ListNode* revHead = nullptr;
    59.         while (cur) {
    60.             ListNode* tmp = cur->next;
    61.             cur->next = revHead;
    62.             revHead = cur;
    63.             cur = tmp;
    64.         }
    66.         return revHead;
    67.     }
    68. };

    时间复杂度：O(n)；反转了三个链表，每个时间复杂度都是O(n)；
    空间复杂度：S(n)；新的链表存储结果，长度为l1和l2中的较长的链表长度（加1）；
    思考：首先想如何不对l1和l2做改变求和，花了20min。最后还是用翻转链表花了15分钟左右。思考了一下，用一个顺序访问的数组存储一下l1和l2的和再进位，然后转换成链表，感觉意义也不是很大。