链表求和

题目描述
假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。
给定两个这种链表，请生成代表两个整数相加值的结果链表。
例如：链表 1 为 9->3->7，链表 2 为 6->3，最后生成新的结果链表为 1->0->0->0。

解法

  //解法：模拟法
    // 1. 高->低位 链表， 反转为，低->高位链表.
    // 2. 模拟两数相加：从低到高，逐位相加进位。
    //时间：O(N)， 空间O（1）
    ListNode* addInList(ListNode* head1, ListNode* head2) {
        if (!head1 || !head2) return head1? head2: head1;
        ListNode* l1 = reverse(head1);
        ListNode* l2 = reverse(head2);
        int carry = 0;
        ListNode dummy(0);
        ListNode* cur = &dummy;
        while (l1 || l2) {
            int v1 = l1? l1->val: 0;
            int v2 = l2? l2->val: 0;
            int v = v1 + v2 + carry;
            cur->next = new ListNode(v % 10);
            carry = v / 10;

            l1 = l1 ? l1->next: nullptr;
            l2 = l2 ? l2->next: nullptr;
            cur = cur->next;
        }
        if (carry != 0) {
            cur->next = new ListNode(carry);
            cur = cur->next;
         }
        return reverse(dummy.next);
    }
    ListNode* reverse(ListNode* head) {
        if (head == nullptr) return head;
        ListNode* cur = head;
        ListNode* prev = nullptr;
        while (cur) {
            ListNode* post = cur->next;
            //反转当前节点
            cur->next = prev;

            //移动游标到下一节点
            prev = cur;
            cur = post;
        }
        return prev;
    }