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

链表相加，是从每个链表的尾部开始相加，如果相加之和大于等于10,就进一位。但是单链表只能遍历下一个结点，所以将两个链表翻转后相加，然后再翻转回来。为了节约空间复杂度，直接将两个链表相加的结果存入第一个链表即可，这里保证第一个链表的长度大于等于第二个链表。最后，如果相加的结果最后一位进一，如9999+1=10000，需要5个结点保存，因此我们应该将得到的结果翻转，然后申请一个结点q,令q的值=1,然后q->next=head。返回q即可。

第二种方法是，借助辅助空间栈

 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 *  ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
#include <cstdlib>
#include <list>
#include <unistd.h>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head1 ListNode类
     * @param head2 ListNode类
     * @return ListNode类
     */
    //先将链表翻转
    ListNode* ReverseList(ListNode* head) {
        if (head == nullptr || head->next == nullptr)
        {
            return head;
        }
            
        ListNode* p = head->next;
        ListNode* t = p->next;
        head->next = nullptr;
        while (p != nullptr) {
            p->next = head;
            head = p;
            p = t;
            if (t != nullptr)
                t = t->next;
        }
        return head;
    }
    int countListLen(ListNode* head)
    {
        int len = 0;
        for(ListNode *p =head;p!=nullptr;p=p->next)
        {
            len++;
        }
        return len;
    }
    ListNode* addInList(ListNode* head1, ListNode* head2) {
        int len1=countListLen(head1);
        int len2=countListLen(head2); //为了方便计算，将短的链表的数据加入到长的链表中
        head1 = ReverseList(head1);
        head2 = ReverseList(head2);
        ListNode* p1;
        ListNode* p2;
        ListNode* temp;
        auto* q = (ListNode*)malloc(sizeof(ListNode)); //如果有进位
        int flag = 0;  //表示是否进一位
        cout<<len1<<"  "<<len2<<endl;
        //始终让head1为长链表
        if (len1 < len2) 
        {
            temp = head1;
            head1 = head2;
            head2 =temp;
        } 
        p1 = head1;
        p2 = head2;
        while (p1 && p2)
        {  //当其中一个走到空结点时，退出循环
            p1->val = p1->val + p2->val + flag; //将数据加到第一个链表
            if (p1->val >= 10) {
                p1->val -= 10;
                flag = 1;
            } else {
                flag = 0;
            }
            p1 = p1 ->next;
            p2 = p2 ->next;
        }
        while(p1)  //如果两个链表长度不一样，p1必定没有走到空结点
        {
            p1->val+=flag;
            if(p1->val>=10)
            {
                p1->val-=10;
                flag = 1;
            }
            else 
            {
                flag = 0;
            }
            p1=p1->next;
        }
        if(flag == 1)  //最后一位还有进位处理
        {
            q->next =nullptr;
            q->val = 1;
            head1 = ReverseList(head1);
            q->next = head1;
            return  q;
        }
        else {
            head1 = ReverseList(head1);
            return  head1;
        }
        
    }
};