[LeetCode] 2.Add Two Numbers (Medium)

//#1 차 2019.04.11

/**  * Definition for singly-linked list.  * struct ListNode {  *     int val;  *     ListNode *next;  *     ListNode(int x) : val(x), next(NULL) {}  * };  */ class Solution { public:     long long powerOfTen(int num)     {         if(num == 0)             return 1;         else             return 10*powerOfTen(num-1);             }     int listToNumbers(ListNode* l){         long long num=0;         long long iDigit=0;         int iTemp=0;         do{             iTemp=0;             iTemp = (unsigned int) l->val * powerOfTen(iDigit);             if(l->next == NULL)             {   num += iTemp;                 return num;             }             l = l->next;             iDigit++;             num += iTemp;         }while(1);                  return num;     }          int lenOfNumber(int num)     {         unsigned int index = 1;         unsigned int temp=0;         do{             temp = (int) (num / powerOfTen(index));             if (temp == 0)                 return index;             index++;         }while(1);     }          int popLeft(long long& num)     {         int len = lenOfNumber(num);         float fTemp = (float)num / powerOfTen(len);         int popVal = fTemp*10;         num = num - popVal*powerOfTen(len-1);         return popVal;     }          int popRight(long long& num)     {         int newNum = num/10;         int popVal = num%10;         num = newNum;         return popVal;     }               ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {         long long left=0, right=0;         long long answer = 0;         int len =0;                  left = listToNumbers(l1);         printf("left=%d\n", left);         right = listToNumbers(l2);         printf("right=%d\n", right);         answer = left + right;                  len = lenOfNumber(answer);                      vector<ListNode*> vecList;                   for(int i=0; i<len; i++)         {             vecList.push_back(new ListNode((int)popRight(answer)));         }                  for(int i=0; i<len-1; i++)         {             vecList[i]->next = vecList[i+1];         }                      return vecList[0];              } };

 

Run Code에서는 정상적으로 나왔지만 submit을 해보니 아주 큰 수로 테스트 하면서 사용하는 변수 보다 더 큰 숫자를 사용하면서 runtime error가 떴다.

해결 방법은 찾아봐야겠다.

 

 

2차. 2019.04.14

너무 복잡한 방법으로 해서 조금 더 쉬운 방법으로 해보았다.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* l3;
        vector<ListNode*> vecList;
        bool bCarrier = false;
        do{
            int sum = l1->val + l2->val;
            printf("sum %d\n",sum);
            if(sum >= 10)
            {
                
                sum = sum - 10;
                printf("inside sum %d\n",sum);
                
                if(true == bCarrier)
                {
                    vecList.push_back(new ListNode(sum+1));
                    bCarrier = false;
                }
                else
                {
                    vecList.push_back(new ListNode(sum));
                }
                
                bCarrier = true;
            }
            else
            {
                if(true == bCarrier)
                {
                    vecList.push_back(new ListNode(sum+1));
                    bCarrier = false;
                }
                else
                {
                    vecList.push_back(new ListNode(sum));
                }
            }
            
            if(NULL == l1->next)
            {
                break;
            }
            l1 = l1->next;
            l2 = l2->next;
        }while(1);
        
        for(int i=0; i<vecList.size(); i++)
        {
            if(i == vecList.size() - 1)
                break;
            vecList[i]->next = vecList[i+1];
        }
        l3 = vecList[0];
        
        
        return l3;
    }
};

 

에잇 길이 다른것 신경 안 썼는데..

다시 해야겠다..ㅠ

 

//3차 2019.04.16 

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* l3;
        vector<ListNode*> vecList;
        bool bCarrier = false;
        bool bl1Last = false;
        bool bl2Last = false;
        do{
            int nl1 = 0;
            int nl2 = 0;
            
            if(false == bl1Last)
            {
                if( l1->next == NULL)
                {
                    bl1Last = true;
                }    
                nl1 = l1->val;
            }
            else
            {
                nl1 = 0;
            }
            
            if(false == bl2Last)
            {
                if( l2->next == NULL)
                {
                    bl2Last = true;
                }    
                nl2 = l2->val;
            }
            else
            {
                nl2 = 0;
            }
            
            int sum = nl1 + nl2;
            printf("sum %d\n",sum);
            if(sum >= 10)
            {
                
                sum = sum - 10;
                printf("inside sum %d\n",sum);
                
                if(true == bCarrier)
                {
                    vecList.push_back(new ListNode(sum+1));
                    bCarrier = false;
                }
                else
                {
                    vecList.push_back(new ListNode(sum));
                }
                
                bCarrier = true;
            }
            else
            {
                if(true == bCarrier)
                {
                    vecList.push_back(new ListNode(sum+1));
                    bCarrier = false;
                }
                else
                {
                    vecList.push_back(new ListNode(sum));
                }
            }
            
            if(NULL == l1->next)
            {
                break;
            }
            
            l1 = l1->next;
            l2 = l2->next;
        }while(1);
        
        for(int i=0; i<vecList.size(); i++)
        {
            if(i == vecList.size() - 1)
                break;
            vecList[i]->next = vecList[i+1];
        }
        l3 = vecList[0];
        
        
        return l3;
    }
};

 

//4차 2019.04.19

드디어 통과...휴..다만..엄청 느림 ㅠㅠ

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    int getLenLN(ListNode* l)
    {
        int len = 0;
        ListNode* lcount = l;
        
        do{
            len += 1;
            lcount = lcount->next;
        }while(lcount != NULL);
        return len;
    }
    
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        
        ListNode* curr = new ListNode(-99);
        ListNode* dummy = curr;
        ListNode* p=l1, *q=l2;
        int carry=0;
        
        int lenl1 = getLenLN(l1);
        int lenl2 = getLenLN(l2);
        
        do
        {
            printf("len1=%d  len2=%d\n", lenl1,lenl2);
            int x = (lenl1 != 0 ) ? p->val : 0;
            int y = (lenl2 != 0 ) ? q->val : 0;
            printf("%d + %d = %d\n", x, y, (x+y)%10);
            int sum = x + y + carry;
            carry = sum / 10;
            if(-99 == curr->val)
            {
                curr->val = sum%10;    
            }
            else
            {
                curr->next = new ListNode(sum%10);
                curr = curr->next;
            }
            
            lenl1 = (lenl1 != 0) ? lenl1-1 : 0;
            lenl2 = (lenl2 != 0) ? lenl2-1 : 0;
            
            p = (lenl1 > 0 ) ? p->next : dummy;
            q = (lenl2 > 0 ) ? q->next : dummy;
            
        }while( lenl1 > 0 || lenl2 > 0);
        
        if(carry != 0)
            curr->next = new ListNode(carry);
        return dummy;
    }

};