思路

1.用数组接收数据
2.逆制，将个位放置0下标处
3.补零
4.相加
5.逆制，恢复最高位放置在下标0处
6.用最终结果创建新链表，并将其返回

class Solution {
public:
    ListNode* addInList(ListNode* head1, ListNode* head2) {
//存在某一链表为空
        if(head1==nullptr)
            return head2;
        if(head2==nullptr)
            return head1;
//用数组接收链表中的数据
        vector<int> arr1,arr2;
        ListNode* p1=head1;
        ListNode* p2=head2;
        while(p1!=nullptr)
        {
            arr1.push_back(p1->val);
            p1=p1->next;
        }
        while(p2!=nullptr)
        {
            arr2.push_back(p2->val);
            p2=p2->next;
        }
//计算需要计算的元素个数分别为多少，并逆制，这样可以保证个位从下标0开始
        int sz1 ,sz2;
        sz1=arr1.size();
        sz2=arr2.size();
        reverse(arr1.begin(), arr1.end());
        reverse(arr2.begin(), arr2.end());
        vector<int> ret;
//给较短的一方补零，保证两个数组一样长
        if(sz1>sz2)//补0
        {
            for(int i=0;i<(sz1-sz2);i++)
                arr2.push_back(0);
        }
        else
        {
            for(int i=0;i<(sz2-sz1);i++)
                arr1.push_back(0);
        }
//得到较长数组的长度，并进行相加过程
        int sz=sz1 > sz2 ? sz1 : sz2;
        for(int i=0;i<sz;i++)
        {
            int sum=0;
            sum=arr1[i]+arr2[i];
            if(sum>9)//结果大于10
            {
                sum%=10;//保留个位
                ret.push_back(sum);
                if(i==sz-1)//如果i处于最后一位，并且还有进位，只能尾部插入1
                    ret.push_back(1);
                else//如果i不是最后一位，只需将下一位+1即可
                    arr1[i+1]+=1;

            }
            else//结果没有进位，则直接插入
            {
                ret.push_back(sum);
            }
        }
//逆转，将最高位转到从0开始
        reverse(ret.begin(), ret.end());
//重新创建链表，将其依次插入
        int szOfRet=ret.size();
        ListNode* head = new ListNode(0);
        ListNode* ptr=head;
        for(int i=0;i<szOfRet;i++)
        {
            ListNode* node=new ListNode(ret[i]);
            ptr->next=node;
            ptr=node;
        }
        //返回最终结果
        return head->next;


    }
};