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

// 解题思路：先求两个链表的长度，然后定义两个指针p1,p2分别指向其链表的头结点；
// 然后 通过 链表的长度 让p1 p2 指向相同的位置(哪个大，就让哪个多走)
// 在这一步顺便将1,2链表多余的那部分压入 vector中，相当于一个栈
// 然后 调用Fun函数，递归的依次将链表相同位置的值加起来并存到head中（注意head为nullptr的情况）
// 最后 通过返回值flag来计算当前是否需要进一位，然后通过vector依次取出栈顶元素链入head中
// 最后当vector为空了，需要判断flag是否为1，若为1，则还需要链一个结点，且其值必为1


    int Length(ListNode* head) // 求链表长度
    {
        int length=0;
        while(head)
        {
            length++;
            head=head->next;
        }
        return length;
    }


    int Fun(ListNode* p1,ListNode* p2,ListNode*& head) // 递归将相同的链入head中
    {
        if(p1->next==nullptr&& p2->next==nullptr)
        {
            int num = p1->val + p2->val;
            ListNode* p =new ListNode(num%10);
            head = p;
            head->next=nullptr;
            if(num>9)
                return 1;
            else
                return -1;
        }
        else 
        {
            int flag = Fun(p1->next,p2->next,head);
            int num  = p1->val+ p2->val;
            if(flag==1)
                num++;
            ListNode* p =new ListNode(num%10);
            p->next=head;
            head=p;
            if(num>9)
                return 1;
            else
                return -1;
        }
    }


    ListNode* addInList(ListNode* head1, ListNode* head2) {
        // write code here
        int length1 = Length(head1);
        int length2 = Length(head2);
        ListNode* p1 =head1,*p2=head2;
        vector<int> vv;
        if(length1>length2)
        {
            for(int i=0;i<length1-length2;i++)
            {  vv.push_back(p1->val);
                p1=p1->next;
            }
        }
        else {
            for(int i=0;i<length2-length1;i++)
                {
                    vv.push_back(p2->val);
                    p2=p2->next;
                }
        }
        ListNode* head=nullptr;
        int flag = Fun(p1,p2,head);
        while(!vv.empty()) // 将多余的那部分取出
        {
            int num = vv[vv.size()-1];
            if(flag ==  1)
                num++;
            ListNode* p =new ListNode(num%10);
            if(head == nullptr)
            {
                head = p;
                head->next=nullptr;
            }
            else {
                p->next=head;
                head = p;
            }
            if(num>9)
                flag=1;
            else
                flag=0;
            vv.pop_back();
        }
        if(flag==1)
        {
            ListNode* p =new ListNode(1);
            p->next=head;
            head=p;
        }
        return head;
    }
};