2. Add Two Numbers

Add Two Numbers 문제는 2개의 Linked List의 합을 구하는 문제입니다.

각 Node에는 0~9 값이 있고, 자리수가 1의 자리부터 증가 합니다.

 

문제는 간단히 한자리씩 더하면서 노드를 만들어 나가면 되는 문제입니다. 단, 처음부터 Number형으로 변경하여 계산 시 Overflow에 빠질 수 있으니 유의해야 합니다.

 

---

 

* Problem

 

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.

 

• Example 1:
  

  

  • Input: l1 = [2,4,3], l2 = [5,6,4]
  • Output: [7,0,8]
  • Explanation: 342 + 465 = 807.
• Example 2:
  • Input: l1 = [0], l2 = [0]
  • Output: [0]
• Example 3:
  • Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
  • Output: [8,9,9,9,0,0,0,1]

 

Constraints:

• 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.

 

---

* Variables

ListNode l1, l2 - Input

ListNode rootNode - Output 용 ListNode, ListNode는 단방향 이므로 return용으로 사용

ListNode currentNode - rootNode에 l1, l2의 값을 더할 목적으로 currentNode 사용

Number over - 각 자리수를 더할 때, 10 이상인 경우 체크목적

 

* Source Code

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function(l1, l2) {
    const rootNode = new ListNode();
    // 숫자로 변형 시킬 경우 overflow 발생, 각 자리수를 계산한 후 10이 넘는 경우 over를 1로 세팅
    // 현재 노드를 root노드로 세팅한 후 시작!
    let over = 0, currentNode = rootNode;
    
    // 더이상 next가 없을 때 까지 반복
    while(l1 !== null || l2 !== null) {
        // next 노드를 생성
        currentNode.next = new ListNode();
        currentNode = currentNode.next;
        
        // l1, l2의 각 노드의 값을 저장. null이라면 0 저장
        let val1 = l1 !== null ? l1.val : 0;
        let val2 = l2 !== null ? l2.val : 0;
        
        // 두 노드의 합을 currentNode에 저장. 이 때, 이 전 노드에서 10이 넘는 경우 1을 추가로 합산
        currentNode.val = val1 + val2 + over;
        // currentNode의 값이 10보다 큰 경우 over를 1로 설정하고, 1의자리만 currentNode에 저장
        if(currentNode.val >= 10) {
            currentNode.val = currentNode.val % 10;
            over = 1;
        }
        else over = 0;
        
        // l1, l2를 각각 다음 노드로 세팅
        if(l1 !== null) l1 = l1.next;
        if(l2 !== null) l2 = l2.next;
    }
    
    // over가 1인 경우 새로운 노드를 생성하고, 값을 1 넣어줌
    if(over === 1) {
        currentNode.next = new ListNode(1);
    }
    
    return rootNode.next;
}

 

---

 

LeetCode의 두 번째 문제를 리뷰하고 있는 현재 20번대 문제 까지 풀이 완료 하였는데, 단순해 보이는 문제도 추후 뒤에 나오는 문제들과 일부분 연결이 되고 있습니다.

이번에 리뷰한 Add Two Numbers의 경우에도 추후 반복적으로 사용될 ListNode의 활용에 중점을 두고 있습니다.

 

 

다음 문제도 크게 어려운 문제는 아니지만, 재밌게 풀 수 있는 문제입니다. ^^;;