문제: https://leetcode.com/problems/add-two-numbers/

문제

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

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

풀이

이 문제는 보자마자 재귀로 풀어야 겠다고 생각했다.
재귀를 통해 차례로 두 수(l1 + l2)의 합을 구하고 return 해주면 된다.

• 고려할 사항.

1. 덧셈 자리 올림에 따른 처리를 해준다.
2. 두 수 중 하나라도 없으면 빠진 채로 덧셈을 진행한다.
3. 두 수 모두 없으면 덧셈을 종료한다.
4. 마지막 수에 덧셈 자리 올림에 따른 처리를 해준다.

코드

class Solution {
	// 두 노드 중 하나만 존재할 때 (add 함수 overloading)
   public ListNode add(ListNode list, ListNode ret) {
//        System.out.println(list.val + " " + ret.val);
        if( list.next != null ) {
            ret.val += list.val;
            if( ret.val < 10 ) {
                ret.next = new ListNode(0);
                return add(list.next,ret.next);
            } else {
                ret.val %= 10;
                ret.next = new ListNode(1);
                return add(list.next,ret.next);
            }
        }
        else {
            ret.val += list.val;
            if( ret.val >= 10 ) {
                ret.val %= 10; 
                ret.next = new ListNode(1);
            }
            return ret;
        }
    }

  // 두 노드 존재할 때 (add 함수 overloading)
    public ListNode add(ListNode l1, ListNode l2, ListNode ret) {
        //System.out.println(l1.val + " " + l2.val + " " + ret.val + " ");
        if( l1.next != null && l2.next != null ) { // 두 노드 모두 next 노드가 존재한다면
            ret.val += l1.val + l2.val;
            if( ret.val < 10 ) { // 덧셈 자리 올림 없는 경우,
                ret.next = new ListNode(0);
                return add(l1.next,l2.next,ret.next);
            } else {	// 덧셈 자리 올림 있는 경우
                ret.val %= 10; 
                ret.next = new ListNode(1);	// 자리 올림 +1
                return add(l1.next,l2.next,ret.next);
            }
        }
        else if( l1.next != null || l2.next != null ) { // 하나의 노드만 next 존재한다면
            ret.val += l1.val + l2.val;
            ListNode next; 
            if( l1.next != null )   next = l1.next;
            else                    next = l2.next;
            
            if( ret.val < 10 ) {
                ret.next = new ListNode(0);
                return add(next,ret.next);
            } else {
                ret.val %= 10;
                ret.next = new ListNode(1);
                return add(next,ret.next);
            }
        }
        else {	 // l1, l2 노드 모두 next 노드가 존재하지 않으면 재귀 종료.
            ret.val += l1.val + l2.val;
            if( ret.val >= 10 ) {	// 자리 올림 처리
                ret.val %= 10;
                ret.next = new ListNode(1);
            }
            return ret;
        }
    }

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode ret = new ListNode(0);
        add(l1,l2,ret);
        return ret;
    }
}