Add Two Numbers

leetcode 문제링크

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

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

• Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
• Output: 7 -> 0 -> 8
• Explanation: 342 + 465 = 807.

나의 풀이

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
// 124ms, 176ms
var addTwoNumbers = function(l1, l2) {
  const arr = [];
  const sum = (l1, l2) => {
    if (l1 && l2) {
      arr.push(l1.val + l2.val)
      sum(l1.next, l2.next);
    } else if (!l2 && l1) {
      arr.push(l1.val)
      sum(l1.next);
    } else if (!l1 && l2) {
      arr.push(l2.val)
      sum(l2.next);
    } else {
      return '';
    }
  }
  sum(l1, l2);
  let over = false;
  const newArr = arr.map((item, idx, arr) => {
    if(item >= 10) {
      arr[idx + 1] != null ? arr[idx + 1] += 1 : over = true
      return item - 10
    } else {
      return item
    }
  });
  if(over) {
    newArr.push(1)
  }
  return newArr;
}

원래 기존 풀이는 200ms인데 좀 줄였다. 연결리스트에 대한 이해가 부족해서 좀 오래 걸렸다.
아래 코드가 굉장히 비효율적이라고 느껴서 위의 코드처럼 다시 만들었는데 그렇게 효율적으로 보이지는 않는다.
나중에 한번 더 다른 방법으로 풀어보고 다른 사람 풀이를 봐야겠다.

// 200ms
var addTwoNumbers = function(l1, l2) {
  const toArray = list => {
    const arr = [];
    const search = node => {
      arr.push(node.val)
      return node.next != null ? search(node.next) : ''
    }
    search(list)
    return arr;
  }
  const arr1 = toArray(l1);
  const arr2 = toArray(l2);
  const large = (arr1.length >= arr2.length ? arr1 : arr2);
  const small = (arr1.length >= arr2.length ? arr2 : arr1);
  const l = large.length;
  const newArr = new Array(l).fill(0);
  const splice = idx => {
    if(newArr[idx + 1] == null) {
      newArr.push(1);
    } else {
      if(newArr[idx + 1] === 9) {
        newArr[idx + 1] = 0;
        splice(idx + 1)
      } else {
        newArr[idx + 1]++;
      }
    }
  }
  for(let i = 0; i < l; i++) {
      if(small[i] == null) {
          const result = newArr[i] + large[i];
          if(result >= 10) {
              splice(i)
              newArr[i] = result - 10;
          } else {
              newArr[i] = result;
          }
      } else {
          const result = large[i] + small[i];
          if(result >= 10 || newArr[i] + result >= 10) {
              splice(i)
              newArr[i] = newArr[i] + (result - 10);
          } else {
              newArr[i] = newArr[i] + result;
          }
      }
  }
  return newArr;
};