链表相加(二)

 这题拿到手上，我一直在考虑一个问题就是，能不能通过不预先遍历的方法去做。

呜呜，原谅我的无知，我想不出来。

那就只能先遍历一遍了，反正也是很不影响时间。

一看到这题，就冒出了两种解题方法，第一种是预先通过两个数组把两个链表中的数据保存下来，然后就变成了大数加法了,然后再把结果放到一个新的链表中。

还一种是补充短的链表，然后进行各个位相加，最后考虑进位。等等，好像不可以吧，如果这样的话，进位没办法解决了，毕竟是一个单链表。如果可行，最后还是要借助数组完成进位。

两种方法我都试一下吧！！！

解法1：开始我想着顺着存，这样就可以在统计长度的时候把数据放入数组中.最后发现进位难处理

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     */
    int *arr1 =  new  int[1000002];        //用来保存结果
    int *arr2 =  new  int[1000002];
    ListNode* addInList(ListNode* head1, ListNode* head2) {
        // write code here
        //末尾对齐,遍历一遍
        int len1 = 0;
        int len2 = 0;
        ListNode *p1 = head1;
        ListNode *p2 = head2;
        
        while(p1 != nullptr)
        {
            p1 = p1->next;      
            len1++;
        }
        while(p2 != nullptr)
        {
            p2 = p2->next;
            len2++;
        }
        
        //将各个数位保存到数组中
        p1 = head1;
        for(int i=len1-1;i>=0;--i)
        {
            arr1[i] = p1->val;
            p1 = p1->next;
        }
        
        p2 = head2;
        for(int i=len2-1;i>=0;--i)
        {
            arr2[i] = p2->val;
            p2 = p2->next;
        }
       
        //各个位相加
        int len = len1 > len2 ? len1:len2;
        for(int i=0;i<len;++i)
        {
            arr1[i] = arr1[i] + arr2[i];
            arr1[i+1] =  arr1[i+1] +  arr1[i]/10;
            arr1[i] = arr1[i]%10;
        }
       
        ListNode *ans = nullptr;
        ListNode *p = nullptr;
        if(arr1[len] > 0)
        {
            ListNode *s = new ListNode(arr1[len]);
            s->next = nullptr;
            ans = s;
            p = s;
        }
        for(int k=len-1;k>=0;k--)
        {
            ListNode *s = new ListNode(arr1[k]);
            s->next = nullptr;
            if(ans == nullptr)
            {
                ans = s;
                p = s;
            }
            else
            {
                 p->next = s;
                 p = p->next;
            }
           
        }
        
        return ans;
    }
};

这里好像忘记释放数组里的内存了，一个好的习惯，还是建议释放掉 

解法2：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     */
    ListNode* addInList(ListNode* head1, ListNode* head2) {
        // write code here
        //末尾对齐,遍历一遍
        int len1 = 0;
        int len2 = 0;
        ListNode *p1 = head1;
        ListNode *p2 = head2;
        
        while(p1 != nullptr)
        {
            p1 = p1->next;      
            len1++;
        }
        while(p2 != nullptr)
        {
            p2 = p2->next;
            len2++;
        }
       
        if(len1 > len2)
        {
            for(int i=0;i<len1-len2;++i)
            {
                ListNode *s = new ListNode(0);
                s->next = head2;
                head2 = s;
            }
        }
        
        if(len2 > len1)
        {
            for(int i=0;i<len2-len1;++i)
            {
                ListNode *s = new ListNode(0);
                s->next = head1;
                head1 = s;
            }
        }
        
        p1 = head1;
        p2 = head2;
        while(p1 != nullptr)
        {
            p1->val = p1->val + p2->val;
            p1 = p1->next;
            p2 = p2->next;
        }
        
        int len = len1 > len2 ? len1:len2;
        int *arr = new int[len+2];
        p1 = head1;
        
        for(int i=len-1;i>=0;--i)
        {
            arr[i] = p1->val;
//             arr[i+1] = arr[i+1] + arr[i]/10;
//             arr[i] = arr[i]%10;
            p1 = p1->next;
        }
        
        for(int i=0;i<len;++i)
        {
            arr[i+1] = arr[i+1] + arr[i]/10;
            arr[i] = arr[i]%10;
        }
        
        ListNode *ans = nullptr;
        ListNode *p = nullptr;
        if(arr[len] > 0)
        {
            ListNode *s = new ListNode(arr[len]);
            s->next = nullptr;
            ans = s;
            p = s;
        }
        
        for(int k=len-1;k>=0;--k)
        {
            ListNode *s = new ListNode(arr[k]);
            s->next = nullptr;
            if(ans == nullptr)
            {
                ans = s;
                p = s;
            }
            else
            {
                p->next = s;
                p = p->next;
            }
        }
        
        delete []arr;
        
        return ans;
    }
};