[LeetCode/MEDIUM] 2. Add Two Numbers (JAVA) : 문제&풀이

 

 

각 자릿수가 하나의 노드로 이루어진 두 리스트노드의 합을 리스트노드로 반환하는 문제이다.
 
두 ListNode를 매개변수로 받는 addTwoNumbers메서드의 틀이 주어진다.

 

Problem :

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        

    }
}

이 때, ListNode의 정의가 다음과 같이 주어진다.

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; }
}

풀이는 addTwoNumbers메서드에 작성하면 된다.
 

 

Solution :

두 숫자 노드의 합을 구해 ListNode로 반환하는 addTwoNumbers 메서드를 콜백 형태로 구현한다.

1. 두 숫자 노드의 합을 구한다.

    이 때, 10으로 나눈 몫이 자리올림수가 된다.

2. 만약 두 노드 다 null이면 null을 반환하고 콜백함수를 빠져나간다.

3. 두 노드 중 하나라도 null이 아니면 ListNode(int val, ListNode next) 생성자를 이용하여 ListNode를 반환한다.

    1) 현재 노드의 값(val) 은 두 숫자 노드 합의 몫이다.

    2) 다음 노드(next)는 addTwoNumbers 메서드를 콜백으로 이용한다.

        - 이 때, 콜백함수 addTwoNumbers에서 다음 노드의 합을 구할 수 있도록
          매개 변수로 주어진 두 ListNode의 다음 노드를 전달한다.

        - 다음 노드가 없으면 null값이 전달된다.

        - 전달 될 두 노드 중 하나에만 앞선 자리올림수를 넘겨 합해주면 된다.

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

    // 두 노드의 합과 자리올림수를 구한다.
    int sum = ((l1 != null) ? l1.val : 0) + ((l2 != null) ? l2.val : 0);
    int carry = sum / 10;

    // 만약 이번 두 노드 모두 null이면 null을 반환하고 콜백 메서드를 빠져나간다.
    if (l1 == null && l2 == null) return null;

    // 두 노드 중 하나라도 null이 아니면
    // 이번 값(val)은 두 노드의 합의 몫으로 하고
    // 다음 연결된 노드는 콜백 형태로 구한다.
    // (이 때 자리 올림 수는 두 다음 노드 중 하나에만 더하면 된다.)
    return new ListNode(
        sum % 10, // val
        addTwoNumbers(getNextNode(l1, carry), getNextNode(l2, 0)) // next
    );
}

// 다음 노드 구하기
private ListNode getNextNode(ListNode l, int carry) {

    // 지금 노드 및 다음 노드가 null이 아니면 자리올림수를 더한 다음 노드를 반환한다.
    if (l != null && l.next != null) {
        l.next.val += carry;
        return l.next;
    }

    // 둘 다 null이고 자리올림수도 없으면 null을 반환한다.
    if (carry == 0) return null;

    // 둘 다 null이지만 자리올림수가 있으면 이 값으로 다음 노드를 만들어 반환한다.
    return new ListNode(carry);

}

 
 

TestCase:

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

Input: l1 = [0], l2 = [0]
Output: [0]

Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]