[Leetcode] 2. Add Two Numbers

Problem

문제 링크

두개의 링크드 리스트(LinkedList)가 주어진다.
링크드리스트는 숫자를 역방향으로 가르키고있다.
두개의 링크드 리스트의 합을 구하고 구한 값을 링크드 리스트로 리턴하는 문제.

여기서는 링크드리스트를 ListNode로 구현해놓음.

// exam )
linkedList : 2 -> 4 -> 3 // 342

Solution

Linked list를 사용하여 데이터를 저장하는 문제.

• 숫자의 범위가 매우 길어 BigInt를 사용하여 수를 계산
• 10으로 나눈 나머지값을 노드 데이터(ListNode)로 만들고 head 노드에 연결함.

1. 파라메타로 내려온 노드를 숫자로 바꾸는 작업.
2. 숫자로 바꾼 두 값을 더함
3. 합한 값에서 10의 나머지를 head 노드에 연결. 그리고 합한 값을 10씩 나눠주면서 자릿수를 줄임.
4. head 노드에 temp를 이용하여 값을들 이어붙임.
5. head 노드의 역할은 첫번째 데이터를 가르키는 역할

JS 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) {
    return toNode(
            toBigNumber(l1) + toBigNumber(l2)
        )

};

const toBigNumber = (node) => {
    let sum = 0n;
    let digit = 1n
    let temp = node
    
    while(temp) {
        sum += BigInt(temp.val) * digit
        temp = temp.next
        digit *= 10n
    }
    
    return sum
}

const toNode = (num) => {
    if (num === 0n) return new ListNode(0)
    
    let head = new ListNode()
    let temp = new ListNode()
    while(num > 0) {
        const last = num % 10n
        temp.next = new ListNode(last)
        if (!head.next) head.next = temp.next
        num /= 10n
        temp = temp.next
    }
    
    return head.next
}