Add two Linked List I && II (Leetcode 2, 445)

Add two Linked List I: https://leetcode.com/problems/add-two-numbers/description/
코드는 어렵지 않다. 교묘하게while loop을 추진하거나 사용해야 한다. 구체적인 코드는 II 아래의 코드와 차이가 많지 않다.
II는 I보다 조금 어려워요. 직접적인 Solution은 Reverse Array예요. 리코드 2 방법으로 해요.

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        if(!l1) return l2;
        else if(!l2) return l1;
        l1 = reverseList(l1);
        l2 = reverseList(l2);
        ListNode *dummy = new ListNode(0);
        ListNode *pre = dummy;
        int carry = 0;
        while(l1 || l2){
            int temp = (l1 ? l1->val : 0) + (l2 ? l2->val : 0);
            int sum = (temp + carry) % 10;
            carry = (temp + carry) / 10;
            ListNode *node = new ListNode(sum);
            pre->next = node;
            pre = node;
            if(l1) l1 = l1->next;
            if(l2) l2 = l2->next;
        } 
        if(carry){
            ListNode *node = new ListNode(1);
            pre->next = node;
            pre = node;
        }
        pre = dummy->next;
        delete dummy;
        return reverseList(pre);
    }
    
    ListNode *reverseList(ListNode* node){
        if(!node) return NULL;
        ListNode *pre = node, *cur = node->next;
        while(cur){
            ListNode *temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp;
        }
        node->next = NULL;
        return pre;
    }
};

Solution II: Stack, Stack은modify 원List가 아니라는 것을 보장할 수 있지만 마지막으로reverse를 한 번 해야 합니다.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        if(!l1) return l2;
        else if(!l2) return l1;
        stack s1, s2;
        ListNode *dummy = new ListNode(0);
        ListNode *pre = dummy;
        while(l1){
            s1.push(l1);
            l1 = l1->next;
        }
        while(l2){
            s2.push(l2);
            l2 = l2->next;
        }
        int carry = 0;
        while(!s1.empty() || !s2.empty()){
            int cur = 0;
            if(!s1.empty()){
                ListNode *n1 = s1.top(); s1.pop();
                cur += n1->val;
            }
            if(!s2.empty()){
                ListNode *n2 = s2.top(); s2.pop();
                cur += n2->val;
            }
            int sum = (cur + carry) % 10;
            carry = (cur + carry) / 10;
            ListNode *node = new ListNode(sum);
            pre->next = node;
            pre = pre->next;
        }
        if(carry){
            ListNode *node = new ListNode(1);
            pre->next = node;
            pre = node;
        }
        pre = dummy->next;
        delete dummy;
        return reverseList(pre);
    }
    
    ListNode *reverseList(ListNode* node){
        if(!node) return NULL;
        ListNode *pre = node, *cur = node->next;
        while(cur){
            ListNode *temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp;
        }
        node->next = NULL;
        return pre;
    }
};

또 실전 시 리커션으로 완성해야 할 수도 있다.Recursion의 요점은 반드시 먼저 한 번 훑어보고 양자의 길이 차이, 그리고 어느 리스트가 더 길었는지 알아야 한다는 것이다. 그렇지 않으면 실현하기 어렵다.

class Solution {
public:
    
    int getLength(ListNode* node){
        int cnt = 0;
        while(node){
            cnt++;
            node = node->next;
        }
        return cnt;
    }
    
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        if(!l1) return l2;
        else if(!l2) return l1;
        int lenA = getLength(l1);
        int lenB = getLength(l2); 
        int carry = 0;
        ListNode *head = (lenA >= lenB) ? sum_util(l1, l2, lenA-lenB, carry) : sum_util(l2, l1, lenB-lenA, carry);
        if(carry){
            ListNode *new_head = new ListNode(1);
            new_head->next = head;
            head = new_head;
        }
        return head;
    }
    
    ListNode *sum_util(ListNode *longer, ListNode *shorter, int offset, int &carry){
        
        if(!longer && !shorter) return NULL;
        ListNode *node = new ListNode(0);
        if(offset == 0){
            node->next = sum_util(longer->next, shorter->next, 0, carry);
            int sum = (longer->val + shorter->val + carry) % 10;
            carry = (longer->val + shorter->val + carry) / 10;
            node->val = sum;
        }else{
            node->next = sum_util(longer->next, shorter, offset-1, carry);
            int sum = (longer->val + carry) % 10;
            carry = (longer->val + carry) / 10;
            node->val = sum;
        }
        return node;
    }
};