2 Add Two Numbers

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

예제

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

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]

해결

생각

• 처음에는 Math.pow(10, 인덱스)로 자리수만큼 곱하고 > 각 수를 더한 후에 > 문자열로 잘라서 반환
  • reduce를 쓰려고 했다
    • const reducer = (accumulator, currentValue, currentIndex) => accumulator + (currentValue * Math.pow(10, currentIndex))
  • 하지만 수자 너무 커지면 scientific notation으로 1e+30처럼 처리가 되고 이걸 문자열로 자르면 10030가 됐다.
  • 큰 수일 경우 수로 계산하면 안 되고, 문자열로 처리해야 한다
• 두번째로는 문자열로 처리했다
  • 합쳐서 1의 자리수만 붙이고
  • 만약 이전 계산에 올림수(carry)가 있다면 더해서 붙인다
  • 현재 체크중인 노드의 다음 노드가 있는지 보고, 없다면 두번째 노드에 수가 남아 있을 수 있으므로 l2를 체크한다.
  • 만들어진 문자열을 반복문으로 돌면서 리스트 노드 만들기
    • 리스트 노드를 애초에 만들면 더 빨라질 수 있을 듯

코드

var addTwoNumbers = function(l1, l2) {
  let totalValue = ""
  let checkNode = l1
  let carry = 0

  while(checkNode) {
    const l1Val = checkNode?.['val'] ? checkNode?.['val'] : 0
    const l2Val = l2?.['val'] ? l2['val'] : 0
    // 둘이 합쳐서 최대는 18
    const total = l1Val + l2Val + (carry > 0? carry : 0)
    const remain = total % 10
    carry = (total / 10) >> 0
    totalValue += remain

    checkNode = checkNode['next']
    if(! checkNode && l2){
      checkNode = l2['next']
      l2 = null
      continue;
    }
    l2 = l2?.['next'] ? l2['next'] : null
  }
  if(carry > 0) {
    totalValue += carry
  }

  let totalValueIdx = totalValue.length -1
  let answer = null; // null로 안해두면 undefined가 들어가서 잘못된 답이라는 에러 발생
  while (totalValueIdx >= 0){
    answer = {
      val: ~~totalValue[totalValueIdx--],
      next: answer
    }
  }

  return answer
};