BM11 链表相加(二)

描述

假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。

给定两个这种链表，请生成代表两个整数相加值的结果链表。

数据范围：0 \le n,m \le 10000000≤n,m≤1000000，链表任意值 0 \le val \le 90≤val≤9

要求：空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)

例如：链表 1 为 9->3->7，链表 2 为 6->3，最后生成新的结果链表为 1->0->0->0。

解题思路：

最自然的做法还是三次翻转：

链表1翻转

链表2翻转

逐位求和（注意进位）

结果使用头插法，避免使用多使用一次翻转，内存O（1），复杂度O（n）

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     */
    
    ListNode *revertList(ListNode *head){
        ListNode *dummy = new ListNode(-1);
        while (head != NULL) {
            ListNode *next = head->next;
            head->next = dummy->next;
            dummy->next = head;
            head = next;
        }
        return dummy->next;
    }

    ListNode* addInList(ListNode* head1, ListNode* head2) {
        // write code here
        ListNode *head11 = revertList(head1);
        ListNode *head12 = revertList(head2);
        ListNode *res = new ListNode(1);
        ListNode *cur = res;
        bool hasAdd = false;
        while(head11 || head12){
            int total = 0;
            ListNode *node;
            if(head11){
                node = head11;
                total += head11->val;
                head11 = head11->next;
            }
            if(head12){
                node = head12;
                total += head12->val;
                head12 = head12->next;
            }
            total = hasAdd ? total + 1 : total;
            hasAdd = total > 9;
            total = total%10;
            node->val = total;
            node->next = res->next;
            res->next = node;
        }
        
        if(hasAdd){
            return res;
        }
        return res->next; 
    }
};