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

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

        while(head2)
        {
            v_2.emplace_back(head2->val);
            head2 = head2->next;
        }
        // 反转数组
        reverse(v_1.begin(),v_1.end());
        reverse(v_2.begin(),v_2.end());
        int len_1 = v_1.size();
        int len_2 = v_2.size();
        int flag = 0;
        vector<int> v;
        for(int i=0; i<max(len_1,len_2); ++i)
        {
            int sum = 0;
            if(i<len_1 && i<len_2)
            {
                sum = (v_1[i]+v_2[i]+flag)%10;
                flag = (v_1[i]+v_2[i]+flag)/10;
            }
            else if(i<len_1)
            {
                sum = (v_1[i]+flag)%10;
                flag = (v_1[i]+flag)/10;
            }
            else
            {
                sum = (v_2[i]+flag)%10;
                flag = (v_2[i]+flag)/10;
            }
            v.emplace_back(sum);
            
        }

        if(flag)
        {
            v.emplace_back(flag);
        }
        // 反转数组
        reverse(v.begin(),v.end());
        // 创建链表
        ListNode* ans = new ListNode(-1);
        ListNode* resut = ans;
        for(int i=0; i<v.size(); ++i)
        {
            ListNode* temp = new ListNode(v[i]);
            ans->next = temp;
            ans = ans->next;
        }

        return resut->next;

        // 方法二：val转为int，相加后创建链表，然后反转链表，但是反转链表老是失败，指针指向何处？最后返回才是重点啊！！！
        // 会超出int的范围
    //     int head_1 = 0, head_2 = 0;
        
    //     while(head1)
    //     {
    //         head_1 = head_1*10+(head1->val);
    //         head1 = head1->next;
    //     }

    //     while(head2)
    //     {
    //         head_2 = head_2*10+(head2->val);
    //         head2 = head2->next;
    //     }

    //     int sum = head_1+head_2;

    //     // 构建链表
    //     ListNode* list_1 = new ListNode(-1);
    //     ListNode* list_2 = list_1;
    //     // list_2 = {-1,0,0,0,1};
    //     while(sum!=0)
    //     {
    //         int temp = sum%10;
    //         ListNode* next = new ListNode(temp);
    //         list_1->next = next;
    //         // 链表节点移动
    //         list_1 = list_1->next;
    //         sum /= 10;
    //     }
    //     // cout << list_2->next->next->next->next->val << endl;
    //     // 反转链表
    //     ListNode* next = nullptr;
    //     ListNode* cur = list_2->next;
    //     // 最终cur变为nullptr
    //     while(cur)
    //     {
    //         ListNode* cur_next = cur->next;
    //         cur->next = next;
    //         next = cur;
    //         cur = cur_next;
    //     }
    //     // 返回这里才是重点啊！！！
    //     return next;
    }
};