题解 | #c++ 哈希表 两个链表生成相加链表#

/**
 * 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* addInList(ListNode* head1, ListNode* head2) {
        // write code here
        /* 方法1:整数相加 不好处理*/
        /* 方法二： 10进制加减  有序哈希表*/
        map<int, int> number1;map<int, int> number2;int index = 0;
        while(head1){
            number1[index++] = head1->val;
            head1 = head1->next;
        }index = 0;
        while(head2){
            number2[index++] = head2->val;
            head2 = head2->next;
        }
        vector<int> renumber;
        map<int,int>::reverse_iterator it1 = number1.rbegin();
        map<int,int>::reverse_iterator it2 = number2.rbegin();
        while(it1!=number1.rend() && it2 != number2.rend()){
            if (it1->second + it2->second >= 10){
                renumber.push_back(it1->second+it2->second -10);
                number1[it1->first -1] += 1;
            }else{
                renumber.push_back(it1->second + it2->second);
            }
            it1++;it2++;
        }while(it1!=number1.rend()){
            if (it1->second >= 10){
                renumber.push_back(it1->second-10);
                if(number1.count(it1->first-1)){
                   number1[it1->first-1] +=1;
                }else{
                    renumber.push_back(1);
                }
            }else{
                renumber.push_back(it1->second);
            }it1++;
        }while(it2!=number2.rend()){
            if (it2->second >= 10){
                renumber.push_back(it2->second-10);
                if(number2.count(it2->first-1)){
                   number2[it2->first-1] +=1;
                }else{
                    renumber.push_back(1);
                }
            }else{
                renumber.push_back(it2->second);
            }it2++;
        }
        //reverse(renumber.begin(), renumber.end());
        ListNode* newhead = new ListNode(0);newhead->next = nullptr;ListNode* p;
        for(auto x : renumber){
            p = new ListNode(x);
            p->next = newhead->next;
            newhead->next = p;
        }
        return newhead->next;
    }
};