리트코드 2. 두개의숫자추가 c++ // stoi 주의점, 노드 begin 저장방법, 두 링크드리스트 덧셈방법

https://leetcode.com/problems/add-two-numbers/description/

 

* stoi 주의점

21억( 2,147,483,647 )== 문자열로 10자리만 벗어나도 out of range 가뜸

-> stoll을 사용할것 ( 9,223,372,036,854,775,807)

-한계 : 20자리이상은 불가능함.

-> 숫자계산으로 구현해야함. 문자열꼼수 안통해

 

* 기존코드

숫자를 문자열로 바꾸면서 덧셈하고

해당 숫자를 다시 노드로 바꿈

- 문제 : stoi 에서 stoll로 해도 ll의 범위도 벗어나버림

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {

        string s1="";
        auto cur = l1;
        while(cur){
            s1+=to_string(cur->val);
            cur=cur->next;
        }
        //cout<<s1;

        string s2="";
        cur = l2;
        while(cur){
            s2+=to_string(cur->val);
            cur=cur->next;
        }
        //cout<<s2;
        reverse(s1.begin(),s1.end());
        reverse(s2.begin(),s2.end());
        long long a = stoll(s1)+stoll(s2); //stoi : out of range!
        //int a =99;
        //cout<<a;
        string s=to_string(a); //807
        reverse(s.begin(),s.end()); //708

        ListNode* ret = new ListNode();
        ListNode* ptr=ret; //첫주소 저장
        for(int i=0;i<s.size();++i){
            //ret->val=s[i]-'0';
            // temp=new ListNode(s[i]-'0');
            // cout<<temp->val<<"\n";
            // temp=temp->next;
            ptr->next = new ListNode(s[i]-'0');
            ptr=ptr->next;
        }

        

        return ret->next;

    }
   
};

 

* 개선의사코드

하나씩 보면서 더해나가고, l1=l1->next로 포인트옮기고, carry를 다음턴으로 넘겨줌

 

빨간 +1이 캐리임

 

 

* 전체코드

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* result = new ListNode(); //begin
        ListNode* ptr = result; //iterator

        int carry=0;

        while(l1 || l2){
            int sum=0+carry; //합 = 이전캐리반영

            if(l1){
                sum+=l1->val;
                l1=l1->next;
            }

            if(l2){
                sum+=l2->val;
                l2=l2->next;
            }

            carry=sum/10; //9+9 =18의 1을넘김
            sum=sum%10;
            ptr->next = new ListNode(sum);
            ptr=ptr->next;
        }

        if(carry==1) ptr->next = new ListNode(1); //캐리가 남은경우
        return result->next;
    }
   
};

 

*노드 begin 저장방법

ptr만 ptr=ptr->next로 조정하면됨.

ListNode* result = new ListNode(); //begin
ListNode* ptr = result; //iterator