Addition of linked lists (2)

 Get this question,One question I've been thinking about is,Can it be done without pre-traversing.

呜呜,原谅我的无知,我想不出来.

Then just traverse it once,It doesn't affect the time anyway.

一看到这题,There are two ways to solve the problem,The first is to save the data in the two linked lists in advance through two arrays,Then it becomes the addition of large numbers,Then put the result into a new linked list.

Another is to add a short linked list,The individual bits are then added,最后考虑进位.等等,好像不可以吧,如果这样的话,Carry can't be solved,It is a singly linked list after all.如果可行,Finally, it is necessary to use the array to complete the carry.

I will try both methods！！！

解法1：At first I thought about saving along the way,In this way, the data can be put into the array when the length is counted.In the end, the carry was found to be difficult to handle

/**
 * 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++;
        }
        
        //Save the individual digits into an array
        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;
        }
       
        //Add the individual bits
        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;
    }
};

It seems that I forgot to free the memory in the array here,一个好的习惯,Still recommend to release it 

解法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;
    }
};