두 숫자 더하기 II | 설명이 있는 Leetcode 문제 해결 방법

문제 설명

두 개의 음수가 아닌 정수를 나타내는 두 개의 비어 있지 않은 연결 목록이 제공됩니다. 가장 중요한 숫자가 먼저 나오고 각 노드에는 한 자리 숫자가 포함됩니다. 두 숫자를 더하고 합계를 연결 리스트로 반환합니다.

숫자 0 자체를 제외하고 두 숫자에 선행 0이 포함되어 있지 않다고 가정할 수 있습니다.

샘플 입력
l1 = [7,2,4,3], l2 = [5,6,4]

샘플 출력
[7,8,0,7]

질문 링크: https://leetcode.com/problems/add-two-numbers-ii/

솔루션(자바)

/**
 * 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) {
        stack<int> n1, n2, sum;
        ListNode *res=new ListNode();
        ListNode *cur=res;
        ListNode *prev;
        int carry=0;
        while(l1!=nullptr) {
            n1.push(l1->val);
            l1=l1->next;
        }
        while(l2!=nullptr) {
            n2.push(l2->val);
            l2=l2->next;
        }
        while(!(n1.empty() && n2.empty())) {
            if(n1.empty()) {
                sum.push((n2.top()+carry)%10);
                carry=(n2.top()+carry)/10;
                n2.pop();
            } 
            else if(n2.empty()) {
                sum.push((n1.top()+carry)%10);
                carry=(n1.top()+carry)/10;
                n1.pop();
            } 
            else {
                sum.push((n2.top()+n1.top()+carry)%10);
                carry=(n1.top()+n2.top()+carry)/10;
                n1.pop();
                n2.pop();
            } 
        }
        if(carry!=0)
            sum.push(carry);
        while(!sum.empty()) {
            cur->val=sum.top();
            cur->next=new ListNode();
            prev=cur;
            cur=cur->next;
            sum.pop();
        }
        prev->next=nullptr;
        return res;
    }
};

설명

먼저 연결된 목록의 숫자를 두 개의 개별 스택으로 푸시합니다. 이것은 연결된 목록을 역순으로 저장하고 추가 작업을 수행하는 데에도 도움이 됩니다. 이제 스택에서 요소를 팝하고 추가하고 합계의 모듈로 10을 세 번째 스택에 푸시하고 합계의 몫 10을 캐리에 저장합니다(유치원에서 사용했던 것처럼 간단한 수학 덧셈). 마지막으로 세 번째 스택에서 요소를 팝하고 세 번째 연결 목록에 삽입하면 결과 연결 목록이 됩니다.