[LeetCode] 2. Add Two Numbers (C++)

Question 2. Add Two Numbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example 1:

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.

Example 2:

Input: l1 = [0], l2 = [0]
Output: [0]

Example 3:

Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]

 

Constraints:

• The number of nodes in each linked list is in the range [1, 100].
• 0 <= Node.val <= 9
• It is guaranteed that the list represents a number that does not have leading zeros.

 

Solution)

해당 문제는 너무 간단하고 단순하게 풀 생각으로 시도했다가 실패했던 문제이다.
처음에는 순수하게 입력데이터 값들을 string 값으로 받아 atoi 또는 atol 함수를 이용하여 숫자로 변형 한 뒤 합을 계산하였다.
여기서 간과했던 것은
The number of nodes in each linked list is in the range [1, 100].
이 부분이었는데 100자리 숫자는 Integer와 long long 타입으로도 커버가 되지 않는다. 

이에 따라 
입력 데이터 ListNode l1, l2 값 들을 하나하나 다 더해가며 next Node를 탐색해야 한다.
-> l1, 또는 l2의 next 노드가 존재하지 않을 때 까지
또 여기서 핵심은 Value값이 10이 넘었을 때 그 next노드 Value값에 +1을 해야 했는데 나는 flag값을 이용하여 이를 처리하였다.

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        
        ListNode* head = new ListNode(); // head 노드 설정
        ListNode* node = head; // ListNode의 head 노드 설정
        int plus = 0; // 10이 넘었을 때 +1의 Flag
        
        while(l1 != nullptr || l2 != nullptr){ // 두개 다 모두 nullptr이 아닐 때 (next값이 존재 할 때 )
            
            int sum = plus;
            
            if(l1 != nullptr) {
                sum += l1 -> val;
            }
            
            if(l2 != nullptr) {
                sum += l2 -> val;
            }
            
            
            if(sum > 9){
                sum = sum % 10;
                plus = 1;
            }
            
            else {
                plus = 0;
            }
            
            ListNode* insert = new ListNode(sum);
            node -> next = insert;
            node = node->next;
            
            l1  = l1 == nullptr ? nullptr : l1->next;
            l2  = l2 == nullptr ? nullptr : l2->next;
            
            if(plus == 1) {
                node -> next = new ListNode(plus); // 10이 넘어가면 그 다음 노드값에 value가 1인 노드를 생성한다.
            }
        
        }
        
        return head->next;
    }
};

 

 

끝.

P.S) 아직까지는 Runtime과 Memory를 생각하지 않고 있는데 다시 C++가 적응되면 그 때는 해당 값들을 신경써야겠다..