Add Two Numbers

|| 문제설명 ||

1. 비어있지 않은 링크드리스트 두 개가 있다.

2. 각 리스트에는 자연수와 0이 역순으로 연결되어있다.

3. 두 링크드리스트를 더한 값이 저장되있는 새로운 링크드리스트를 반환하여라.

4. 이때 맨 앞자리는 0이 아니다.

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

• Input

  ListNode* l1
   ListNode* l2

• Output

  ListNode*

---

|| 문제해결과정 ||

ListNode* answer;

1) O(n)

- 올림수가 있는지 없는지 알려줄 upper과 l1, l2가 각각 끝났는지 알려주는 e1, e2
- 두 링크드리스트가 종료할 때까지 while문으로 돌려준다.
- 먼저 링크드리스트들이 종료되는지 확인하고 종료가 되지 않았다면 각 리스트의 val을 더한 뒤 %10을 통해 나머지((v1 + v2 + upper) % 10)만을 새로운 리스트(tmp)의 val에 저장
- (l1->val + l2->val) / 10가 1인지 0인지 판단하여 upper에 1 or 0을 넣어준다.
- l1, l2을 각각 다음 연결로 바꿔준다.
- tmp의 위치도 tmp->next로 바꿔준다.

---

|| 코드 ||

[2020.10.01] 실패

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* answer, *tmp;
        int upper = 0, e1 = 0, e2 = 0;
        answer = tmp;
        while(1) {           
            int v1 = 0, v2 = 0;
            
            // l1, l2의 종료 여부 판단
            if(!e1) {
                if(l1 != nullptr) v1 = l1->val;
                else e1 = 1;
            }
            if(!e2) {
                if(l2 != nullptr) v2 = l2->val;
                else e2 = 1;
            }
            if(e1 + e2 == 2) break;
            
            // l1 + l2
            tmp->val = (v1 + v2 + upper) % 10;
            if((l1->val + l2->val) / 10) upper = 1;
            else upper = 0;
            
            // 다음 위치로 이동
            tmp = tmp->next;
            l1 = l1->next;
            l2 = l2->next;
        }
        return answer;
    }
};

ListNode를 answer, tmp를 제외하고 하나라도 더 쓰면 메모리 부족 → 동적메모리 할당을 이용한 새로운 ListNode를 통해 주소 오류 해결

[2020.10.01] 실패

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* answer = NULL, * tmp;
        int carry = 0, v = 0;
        bool e1 = false, e2 = false;
        while(1) {           
            int v1 = 0, v2 = 0;
           
            if(!e1) l1 != NULL ? v1 = l1->val : e1 = true;
            if(!e2) l2 != NULL ? v2 = l2->val : e2 = true;
            
            v = (v1 + v2 + carry) % 10;
            ListNode * tmp1 = new ListNode(v);
            carry = ((v1 + v2 + carry) / 10) ? 1 : 0;

            if(e1 && e2) break;	// 올림수가 존재하는지에 대한 조사
            
            if(answer == NULL) {
                answer = tmp1;
                tmp = tmp1;
            }
            else {
                tmp->next = tmp1;
                tmp = tmp1;
            }
        
            if(!e1) l1 = l1->next;
            if(!e2) l2 = l2->next;
        }
        // 마지막 올림수에 대한 덧셈
        if(carry) {
            ListNode * tmp1 = new ListNode(1);
            tmp->next = tmp1;
        }
        return answer;
    }
};

Input : [5], [5] | Output : [0] | Expected : [0, 1]

종료 조건문의 위치가 잘못되었다.
착각.....해버렸...
e1과 e2가 모두 true로 바뀌는 그 순간 바로 종료해야한다.
그 뒤로 갈 시에는 무조건 v = 1으로 carry가 0이 되어 마지막 if(carry)문이 작동되지 않는다.

[2020.10.01] 성공

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* answer = NULL, * tmp;
        int carry = 0, v = 0;
        bool e1 = false, e2 = false;
        while(1) {           
            int v1 = 0, v2 = 0;
           
            if(!e1) l1 != NULL ? v1 = l1->val : e1 = true;
            if(!e2) l2 != NULL ? v2 = l2->val : e2 = true;
            if(e1 && e2) break;
            
            v = (v1 + v2 + carry) % 10;
            ListNode * tmp1 = new ListNode(v);
            carry = ((v1 + v2 + carry) >= 10) ? 1 : 0;
            
            if(answer == NULL) {
                answer = tmp1;
                tmp = tmp1;
            }
            else {
                tmp->next = tmp1;
                tmp = tmp1;
            }
        
            if(!e1) l1 = l1->next;
            if(!e2) l2 = l2->next;
        }
        if(carry) {
            ListNode * tmp1 = new ListNode(1);
            tmp->next = tmp1;
        }
        return answer;
    }
};

---

1) 평가

---

2) 시간 & 메모리

---

[2020.10.01] 약 10초 감속.ver

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* answer, * tmp = new ListNode;
        int carry = 0, v = 0;
        answer = tmp;	//  return answer; 대신 answer->next로 바뀌는 대신 while(l1 && l2)에서의 조건문이 사라짐.
        
        // 새로운 변수에 동적할당받는 대신 바로 동적할당
        while(l1 && l2) {           
            v = (l1->val + l2->val + carry) % 10;            
            carry = (l1->val + l2->val + carry) / 10;
           
            tmp->next = new ListNode(v);
            tmp = tmp->next;
            l1 = l1->next;
            l2 = l2->next;
        }
        while(l1) {
            v = (l1->val + carry) % 10;
            carry = (l1->val + carry) / 10;
            tmp->next = new ListNode(v);
            tmp = tmp->next;
            l1 = l1->next;
        }
        while(l2) {
            v = (l2->val + carry) % 10;
            carry = (l2->val + carry) / 10;
            tmp->next = new ListNode(v);
            tmp = tmp->next;
            l2 = l2->next;
        }
        if(carry) tmp->next = new ListNode(1);

        return answer->next;
    }
};