Leetcode - 2. Add Two Numbers

문제

주어진 두 링크드 리스트는 각각 10진수 수를 나타낸다(역방향) 가령 [2,4,3]는 342를 나타냄.
두 값의 합을 리스트로 리턴하라.

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.

해결

/*
1. in two linked list [2,4,3], [5,6,4]
out : sum of two list 

2. test plan
Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
[4] [6]
[0, 1]

3. data structure / algorithm
DS: linked list
ALGO: 
 - add value (with carry value)
 for() l1 != NULL; l1 = l1->next, l2 = l2->next)
    sum = l1 + l2
    ret = add_list(sum)

*/

struct ListNode* new_node(int val)
{
    struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
    node->val = val;
    node->next = NULL;
    return node;
}

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
    struct ListNode* ret = new_node(0);
     struct ListNode* save_ret = ret;
    int carry = 0;
    
    while (l1 || l2 || carry) {
        int sum = 0;
        if (l1) {
            sum += l1->val;
            l1 = l1->next;
        }
        if (l2) {
            sum += l2->val;
            l2 = l2->next;
        }
        if (carry)
            sum += carry;
        carry = (sum > 9) ? 1: 0;
        ret->next = new_node(sum % 10);
        ret = ret->next;            
    }
    return save_ret->next;
}

해결 220905

나중에 다시 c++ 로 풀어봤는데, 이전에 풀었던 방식과 똑같음.. 오히려 코드 복잡도 측면에서 약간 퇴보. 잘하자.

class Solution {
    ListNode *add_node(int val) {
        ListNode *node = new ListNode;
        node->val = val;
        node->next = NULL;
        return node;
    }
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode *head = add_node(0);
        ListNode *node = head;
        int carry = 0;
        
        while (l1 || l2) {
            int calc = carry;
            if (l1) {
                calc += l1->val;
                l1 = l1->next;
            }
            if (l2) {
                calc += l2->val;
                l2 = l2->next;
            }
            if (calc > 9)
                carry = 1;
            else 
                carry = 0;
            calc = calc % 10;
            
            node->next = add_node(calc);
            node = node->next;
        }
        if (carry == 1)
            node->next = add_node(carry);
        
        return head->next;
    }
};