[ leetcode ] 445. Add Two Numbers II

해당 문제는 두 Linked List가 주어지고, 각 링크드 리스트의 노드는 숫자를 나타내고 있으며 각 숫자는 head 부터 tail까지 한 숫자의 각 자릿수를 나타냅니다.

두 링크드 리스트의 숫자를 더한 결과의 링크드 리스트를 반환하는 문제입니다. 

일반적으로 두 수의 덧셈은 가장 아랫자리부터 덧셈이 이루어지므로 stack에 각 링크드 리스트의 숫자를 넣어 가장 아랫자리부터 나올 수 있도록 준비하고 덧셈의 결과 값도 마찬가지로 stack에 넣어 링크드 리스트로 하나씩 빼내며 만들 수 있습니다.

 

/**
 * 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) {}
 * };
 */
#include <stack>

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        stack<int> one, two, answer;
        while (l1) one.push(l1->val), l1 = l1->next;
        while (l2) two.push(l2->val), l2 = l2->next;
        
        int carry = 0;
        while (!one.empty() || !two.empty()) {
            int num1 = one.empty() ? 0 : one.top();
            if (!one.empty()) one.pop();
            int num2 = two.empty() ? 0 : two.top();
            if (!two.empty()) two.pop();
            int sum = carry + num1 + num2;
            carry = sum / 10;
            answer.push(sum % 10);
        }
        if (carry) answer.push(carry);
        ListNode* head = new ListNode(answer.top());
        answer.pop();
        ListNode* temp = head;
        while (!answer.empty()) {
            temp->next = new ListNode(answer.top());
            temp = temp->next;
            answer.pop();
        }
        return head;
    }
};