2. Add Two Numbers

Intuition

1. 두 ListNode를 돌면서 각각 배열로 받는다
2. 배열로 받은 애들을 for문으로 숫자?로 바꾼다. (저 숫자를 뭐라고 하지요....)
3. 숫자로 받으면 그걸 다시 ListNode로 변경한다.
4. 끝.
5. 오버플로우

Approach

재귀로 풀어야 한다는 소식을 듣고 풀이 방향 전격 변경 !!
1. 두 ListNode를 동시에 돌린다.
- 동시에 현재 노드값, 받아올림 값을 더한다(sum)
- sum이 10보다 큰지 확인한다. (곱이 아니라 합이므로 10 안에서 해결 가능)
- 받아올림 상황(sum / 10 == 1하면 될 듯): 받아올림을 위해 carry++를 해준다
- 받아올림이 아닌 상황: carry에 +1을 추가하지 않는다.
- ans ListNode 현재 노드에 sum%10한 값을 넣는다.
- return 값으로 node 두 개와 carry를 넣는다. (고민되는 부분: carry 대신 sum을 넣어도 괜찮지 않을까?)
- 한쪽 노드가 이미 끝난 경우
- if문을 사용해서 sum 처리하고 바로 return시킨다.

2. 돌릴 때 같은 순서의 노드끼리 더한다.
   • 받아올림이 발생할 경우, 다음 노드로 이동했을 때 더해준다. (해당 방법의 장점: overflow 발생하지 않음!)
3. 문제 발생! 두 노드의 길이가 같지 않은 경우
   • 중간에 더하는 걸 그만두고 남은 걸 한 번에 더해주거나, 아니면 그냥 끝까지 돌더라도 짧은 ListNode가 null이나 아무튼 그런 상황에 처하는 걸 막는다. (NullPointException 방지)
4. 최종 정렬된 ListNode를 return해준다.

Complexity

• Time complexity: O(n)
• Space complexity: O(n)

Code

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

 // 새로운 목표: 무조건 재귀 1회 이상 사용 
class Solution {
    ListNode dummy = new ListNode(0); 
    ListNode ans = dummy;
    ListNode a = new ListNode(0);
    ListNode b = new ListNode(0);

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        a.next = l1;
        b.next = l2;
        if (plusNode(0) == 1){
            ans.next = new ListNode(1);
            return dummy.next;
        }else{
            return dummy.next;
        }
    }


    public int plusNode(int carry){ 
        int sum = 0; // 나중에 옮기기 -> 옮기면 안돼!
        if (a.next == null || b.next == null){ // 한쪽 노드가 이미 끝난 경우 
            if(a.next == null && b.next == null){
                return carry; 
            }else if(a.next == null){
                sum = b.next.val + carry; 
                b = b.next;
                ans.next = new ListNode(sum % 10);
                ans = ans.next;
                return plusNode(sum / 10);
            }else{ // b.next == null
                sum = a.next.val + carry;
                a = a.next; 
                ans.next = new ListNode(sum % 10);
                ans = ans.next;
                return plusNode(sum / 10);
            }

        }else{
            sum = a.next.val + b.next.val + carry;

            if (sum / 10 == 1){ // 받아올림 상황
                ans.next = new ListNode(sum % 10);
                ans = ans.next; 
                a = a.next;
                b = b.next;
                return plusNode(1);
            }else{ // 받아올림 아님 상황
                ans.next = new ListNode(sum % 10);
                ans = ans.next;
                a = a.next;
                b = b.next;
                return plusNode(0);
            }
        }        
    }
}

아쉬운 점

• 전역 변수를 사용한 점
• 코드가 너무 쓸데없는 내용이 많다. 마지막 if문만 해도 하나로 묶을 수 있는 상황이었다.