[LeetCode, 리트코드] Add Two Numbers

1. Problem

 

음이 아닌 정수를 나타내는 비어 있지 않은 두 연결 리스트들이 주어진다. 각 숫자들은 역배열로 저장되어 있으며 각 리스트의 노드들은 하나의 0-9까지의 숫자를 가지고 있다. 두 링크드 리스트들이 나타내는 두 숫자들을 더하고 그것을 링크드 리스트 형태로 반환하라

0가 먼저 나오는 경우는 제외한다. 단 0 그 자체인 경우는 허용된다.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

2. Solution

 

이 문제는 Merge Sort를 구현한 적이 있다면 쉽게 풀 수 있다. 왜냐하면 Merge 부분의 알고리즘과 흡사하기 때문. for loop나 while loop를 이용하는 것이 이 문제의 해결책이다. 중요부분은 null point 체크와 덧셈 올림 체크다. l1 l2 리스트들의 요소를 모두 계산했을 때, 마지막 올림수가 1이 됬을 경우 이 부분을 반영하는 것을 조심해야한다.

3. What I solved

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* ret = new ListNode(-99999);
        ListNode* p;
        p = ret;
        int carry = 0;
        int sum, remain;
        while(l1 != nullptr && l2 != nullptr){
            sum = l1->val + l2->val + carry;
            carry = sum / 10;
            remain = sum % 10;
            p->next = new ListNode(remain);
            p = p->next;
            l1 = l1->next;
            l2 = l2->next;
        }
        
        if(l1 != nullptr){
            while(l1 != nullptr){
                sum = l1->val + carry;
                carry = sum/10;
                remain = sum % 10;
                p->next = new ListNode(remain);
                p = p->next;
                l1 = l1->next;
            }
        }
        else if(l2 != nullptr){
            while(l2 != nullptr){
                sum = l2->val + carry;
                carry = sum/10;
                remain = sum % 10;
                p->next = new ListNode(remain);
                p = p->next;
                l2 = l2->next;
            }
        }
        
        if(carry == 1){
            p->next = new ListNode(1);
            p = p->next;
        }
        
        return ret->next;
    }
};

4. Best Solution

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode *c1 = l1, *c2 = l2, *head = nullptr, *prev = nullptr;
        short c = 0;
        while(c1 || c2 || c){
            c += (c1 ? c1->val : 0);
            c += (c2 ? c2->val : 0);
            ListNode *cur = new ListNode(c % 10);
            c /= 10;
            if(!head) head = cur;
            if(prev) prev->next = cur;
            prev = cur;
            if(c1) c1 = c1->next;
            if(c2) c2 = c2->next;
        }
        return head;
    }
};