[Linked List] Add Two Numbers

2. Add Two Numbers

지문은 링크에서 확인해주세요.

1. 해답을 보지 않고 스스로 문제를 해결한 과정

/**
 * 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}
 
 * Runtime	: 80 ms
 * Memory	: 47.49 MB
 */
var addTwoNumbers = function(l1, l2) {
  let lcur = new ListNode(0);  
  const lans = lcur;

  let carry = 0;

  while(l1 || l2 || carry > 0) {
    let sum = 0;

    if(l1) {
      sum += l1.val;
      l1 = l1.next;
    }

    if(l2) {
      sum += l2.val;
      l2 = l2.next;
    }
        
    sum += carry;
    carry = ~~(sum / 10) 

    const val = sum % 10;
    lcur.next = new ListNode(val);
    lcur = lcur.next;    
  }
  
  return lans.next;
};

본 해답을 찾기 전까지, 불필요한 노드를 생성하고 루프가 종료되었습니다.

Example 1:
Output		: [7,0,8,0]
Expected	: [7,0,8]

따라서 현재 구한 합은 다음 노드의 val로 넘겨주는 방식으로 루프를 종료하였습니다. 해답으로 건네는 연결리스트도 실제로는 [0,7,0,8] 와 같은 노드로 이루어져 있지만, head.next 부터 해답을 검증하도록 하였습니다.

2. 여러 해답을 직접 찾아서 자신이 작성한 알고리즘에 대해서 회고한 내용

2-1. Using recursion

해답의 전문은 링크를 확인해주세요.

/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @param {number} carry
 * @return {ListNode}
 
 * Runtime	: 87 ms
 * Memory	: 47.63 MB
 */
var addTwoNumbers = function(l1, l2, carry) {
    if(!l1 && !l2 && !carry) return null;

    var total = (l1 ? l1.val : 0) + (l2 ? l2.val : 0) + (carry || 0);
    carry = parseInt(total / 10);
    return new ListNode(total % 10, addTwoNumbers(l1?.next, l2?.next, carry));
};

제출 함수에 인자를 추가하고, 재귀로 사용한 점이 인상적이었습니다.