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

我又来啦~

这一道题思路还是很简单的，其实就是一个简单的竖式加法。由于对于时间复杂度和空间复杂度的要求都非常宽容，因此很容易就想出解决算法。

由于竖式加法需要从链表的尾节点开始，如果一次又一次遍历到尾节点再做加法的化，时间复杂度很容易来到O(n^2)

所以，我们选择遍历两次次链表即可，即第一次来获取链表的长度(qaqC语言中没有在顶以后可变长的数组，也不能使用C++中方便的容器)，第二次遍历来将链表中的val存入数组中。

这样我们可以通过数组来实现竖式加法。

需要注意的是，由于竖式加法是右对齐的，并且参与运算的链表的长度不一，我们需要倒叙存储哦，即index=0时存储的是最低位的数。

进行竖式加法时需要注意的就是，1.结果数组的位数；2.结果开头的0如何处理

由于需要考虑进位的问题，所以结果数组的位数需要是参与运算的最长的数组的长度＋1；

对于开头0的问题，当计算到这个位置的输出时，参与运算的两个链表其实已经没有对应的位数了(即全部是0)，此时影响结果的是补位的那个数，如果这个数也为0，则说明结果开头会出现一个0， 此时简单粗暴的方法就是将结果的最大长度--，这样后面创建新链表时，就会忽略index=max-1的这个数。

struct ListNode* createnode(int val)
{
    struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
    if(node!=NULL)
    {
        node->val = val;
        node->next = NULL;
        return node;
    }
    return NULL;
}
int getlen(struct ListNode* head)
{
    int len = 0;
    while(head!=NULL)
    {
        len++;
        head = head->next;
    }
    return len;
}
struct ListNode* addInList(struct ListNode* head1, struct ListNode* head2 ) {
    // write code here
    int len1 = getlen(head1);
    int len2 = getlen(head2);
    if(len1==0)
    {
        return head2;
    }
    if(len2==0)
    {
        return head1;
    }
    int num1[len1];
    int num2[len2];
    for(int i=len1-1;i>=0;i--)
    {
        num1[i] = head1->val;
        head1 = head1->next;
    }
    for(int i=len2-1;i>=0;i--)
    {
        num2[i] = head2->val;
        head2 = head2->next;
    }
    int max;
    if(len1>len2)
    {
        max=len1+1;
    }
    else
    {
        max = len2+1;
    }
    int out[max];
    for(int i=0;i<max;i++)
    {
        out[i] = 0;
    }
    int comp = 0 ;
    for(int i=0;i<max;i++)
    {
        if(i<len1&&i<len2)
        {
            out[i] = (num1[i]+num2[i]+comp)%10;
            comp = (num1[i]+num2[i]+comp)/10;
        }
        if(i<len1&&i>=len2)
        {
            out[i] = (num1[i]+comp)%10;
            comp = (num1[i]+comp)/10;
        }
        if(i>=len1&&i<len2)
        {
            out[i] = (num2[i]+comp)%10;
            comp = (num2[i]+comp)/10;
        }
        if(i>=len1&&i>=len2)
        {
            if(comp==0)
            {
                max--;
            }
            else 
            {
                out[i] = (comp)%10;
                comp = (comp)/10;      
            }
        }
    }
    struct ListNode* newhead = createnode(out[max-1]);
    struct ListNode* output = newhead;
    for(int i=max-2;i>=0;i--)
    {
        struct ListNode* newnode = createnode(out[i]);
        if(newnode!=NULL)
        {
            newhead->next = newnode;
            newhead = newhead->next;
        }
    }
    return output;
}