Add Two Numbers

🔗 문제 링크

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 contains a single digit. Add the two numbers and return the sum as a linked list.

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

⚠️ 제한사항

• The number of nodes in each linked list is in the range [1, 100].

• 0 <= Node.val <= 9

• It is guaranteed that the list represents a number that does not have leading zeros.

---

🗝 풀이 (언어 : Java)

어려웠던 문제였다. 처음에 숫자를 String으로 바꾸고 StringBuilder의 reverse를 이용하여 뒤집고 덧셈후 다시 Long.valueOf()로 숫자로 바꿔주려고 했다. 하지만 NumberFormatException이 발생했다. 앞에 0이 오는 케이스 때문이 아닌, 정수 자료형의 범위를 넘는 숫자 문자열을 정수로 변환하려해서 발생한 에러였다. 문제 조건에서 숫자 원소 개수가 100개까지 가능하다. 이건 long의 범위도 넘기 때문에, 위와 같은 방식으로는 풀이가 불가능했다. 그리고 문제 종류가 LinkedList 문제였는데, LinkedList 자료형이 아닌, 정의한 Node를 이용한 LinkedList였다. 처음 노드 주소값을 어떻게 보관하면서 뒤에 노드들을 차례로 넣어주는지 방법이 떠오르지 않았다.

풀이를 보고 다시 작성해보았는데, 정답은 숫자 하나씩 뽑아서 올림수와 해당 자리수를 분리해서 결과 노드에 넣어주고, 처음 노드를 담는 변수를 선언하고 그 노드를 담는 또다른 변수를 선언해준 후에 이 두번째 변수를 이용해서 계속 재할당하면서 뒤에 노드를 이어 붙였고, 처음 노드는 첫번째 변수에 남아있는 알고리즘이었다. 이번 기회에 이러한 자료형을 다루는 법을 조금은 배운 것 같아 좋았다.

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(), tmp = head;
        int carry = 0;
        while (l1 != null || l2 != null) {
            int x = (l1 == null) ? 0 : l1.val;
            int y = (l2 == null) ? 0 : l2.val;
            tmp.next = new ListNode((x+y+carry) % 10);
            carry = (x + y + carry) / 10;
            tmp = tmp.next;
            if (l1 != null)
                l1 = l1.next;
            if (l2 != null)
                l2 = l2.next;
        }
        if (carry > 0)
            tmp.next = new ListNode(carry);
        return head.next;
    }
}