题解 | #链表相加(二)#

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 *  ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
#include <asm-generic/errno.h>
#include <cstdlib>
#include <list>
#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head1 ListNode类
     * @param head2 ListNode类
     * @return ListNode类
     */
    ListNode* addInList(ListNode* head1, ListNode* head2) {
        // write code here
        if (head1 == nullptr) {
            return head2;
        } else if (head2 == nullptr) {
            return head1;
        }

        // 遍历，求链表长度
        int listSize1 = listLen(head1);
        int listSize2 = listLen(head2);

        // 计算
        if (listSize1 >= listSize2) {
            return calVal(head1, listSize1, head2, listSize2);
        } else {
            return calVal(head2, listSize2, head1, listSize1);
        }

    }


    int listLen(ListNode* head) {
        ListNode* p = head;
        int listSize = 1;
        while (p->next) {
            p = p->next;
            listSize++;
        }
        return listSize;
    }

    ListNode* calVal(ListNode* longList, int longSize, ListNode* shortList,
                     int shortSize) {

        vector<int> saveVal;  // 保存进位
        saveVal.push_back(0);


        ListNode* l = longList;
        ListNode* s = shortList;

        // 利用vector保存计算结果
        while (l || s) {
            if (longSize-- > shortSize) {
                saveVal.push_back(l->val);
                l = l->next;
                continue;
            }
            saveVal.push_back(l->val + s->val); // 十位数
            l = l->next;
            s = s->next;
        }

        ListNode* preHead = new ListNode(0);
        preHead->next = nullptr;

        ListNode* nxt = nullptr;

        for (int i = saveVal.size()-1; i >= 0 ; i--) {
            if (saveVal.at(i) > 9) {
                saveVal.at(i-1) += saveVal.at(i) / 10;
                saveVal.at(i) = saveVal.at(i) % 10;
            }
            ListNode* node = new ListNode(saveVal.at(i));
            node->next = nxt;
            preHead->next = node;
            nxt = node;
        }

        if(preHead->next->val != 0) {
            return preHead->next;
        } else {
            return preHead->next->next;
        }
        
    }

};