[leetcode 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]

 

문제:

두 개의 리스트가 주어지면 각 노드의 합을 구한다. 단 리스트 방향이 거꾸로이므로 더해서 10이 넘어갈 경우 다음 노드에서 이것을 고려해줘야 한다.

 

풀이:

- 리스트 + carry

- 첨에 트리 문제처럼 한 쪽 리스트에 더했다가 틀림. 이 문제는 마지막 노드에서 합이 >10인 경우 새로운 노드를 생성해줘야 하기 때문에 처음부터 새로운 노드 리스트에 담는 것이 낫다.

- 끝나는 조건은 두 리스트 모두 nullptr를 가리킬 때. 하나라도 nullptr이 아니면 계속 계산해야 한다. 예시 3번처럼 carry가 계속 1인 경우가 있기 때문

- c++ new 문법: c++에선 굳이 malloc를 안해줘도 new를 사용해서 포인터 선언이 가능하다! 초기값 설정도 가능

ListNode* cur = new ListNode(0);

이런 식으로

/**
 * 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) {
        
        int sum = 0, carry = 0;
        
        ListNode *curr = new ListNode(0);
        ListNode *result = curr;
        
        while(l1 != nullptr || l2 != nullptr){
            sum = carry;
            
            if(l1 != nullptr){
                sum += l1->val;
                l1 = l1->next;
            }
            
            if(l2 != nullptr){
                sum += l2->val;
                l2 = l2->next;
            }
            
            carry = sum/10;
            curr->next = new ListNode(sum%10);
            curr = curr->next;
        }
        
        if(carry == 1){
            curr->next = new ListNode(carry);
        }
        
        return result->next;
    }
};