2. add-two-numbers https://leetcode.com/problems/add-two-numbers/

Medium

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.

숫자 0을 제외하고 두 숫자에 선행 0이 없다고 가정할 수 있습니다.

Example 1:

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

Example 2:

Input: l1 = [0], l2 = [0]
Output: [0]
Plain Text
복사

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]
Plain Text
복사

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.

각 링크된 목록의 노드 수는 [1, 100] 범위에 있습니다.

0 <= Node.val <= 9

목록은 선행 0이 없는 숫자를 나타냅니다.

My solution

next라는 배열을 만들어서 두 연결리스트를 담아둔다.

next라는 배열이 연결리스트를 하나도 가지고 있지 않다면 그때 while문이 끝난다.

while (next.length) {
    const [firstNode, secondNode] = next;
JavaScript
복사

결과 리스트를 담아두는 배열. result[0]에는 노드가 가장 많은 완성된 리스트에 접근할 수 있다.

  // 배열 시작에 노드를 추가한다.
  // 노드들을 연결한다.
  const addNode = val => {
    const prev = result[result.length - 1];
    const node = new ListNode(Number(val));
    result.push(node);
    if (prev) {
      prev.next = node;
    }
  };
JavaScript
복사

노드를 어떻게 추가해줘야할지? 위의 addNode 함수를 만들어야 한다. result라는 배열을 만들었다. 어려운 것은 이미 result가 존재하는지 보고 그 마지막 노드의 next에 새로운 노드를 연결해주어야 한다는 것이다.

Code

function ListNode(val, next) {
  this.val = val === undefined ? 0 : val;
  this.next = next === undefined ? null : next;
}
/**
 * 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}
 */
const addTwoNumbers = function (l1, l2) {
  // O(n) time | O(n) space
  let next = [l1, l2];
  const result = [];
  let carry = 0;

  // 배열 시작에 노드를 추가한다.
  // 노드들을 연결한다.
  const addNode = val => {
    const prev = result[result.length - 1];
    const node = new ListNode(Number(val));
    result.push(node);
    if (prev) {
      prev.next = node;
    }
  };

  while (next.length) {
    const [firstNode, secondNode] = next;
    // 노드가 존재할 때 그 값을 val1, val2에 저장한다.
    const val1 = (firstNode || {}).val || 0;
    const val2 = (secondNode || {}).val || 0;
    // 두 노드 각각이 가리키는 next를 firstNext, secondNext에 저장한다.
    const firstNext = (firstNode || {}).next;
    const secondNext = (secondNode || {}).next;
    // undefined가 아니라면 hasNext를 true로 바꾼다.
    const hasNext = firstNext || secondNext;
    // carry는 0에서부터
    const sum = val1 + val2 + carry;
    // & : sum이 10보다 작으면 carry는 null(0), 그렇지 않으면 carry는 10의 자리를 반환한다.
    const [toCarry, digit] = sum < 10 ? [null, sum] : (sum + '').split('');

    carry = Number(toCarry);
    // & : 다음 노드가 존재하면 next를 업데이트한다.
    next = firstNext || secondNext ? [firstNext, secondNext] : [];
    // 계산한 값은 result 배열에 노드로 추가한다.
    addNode(digit);
    // & : 다음 노드가 존재하지 않으면 carry를 지금 넣고 리턴해야 한다.
    if (!hasNext && carry) {
      addNode(carry);
    }
  }

  return result[0];
};

test('TC1', () => {
  expect(addTwoNumbers([2, 4, 3], [5, 6, 4])).toStrictEqual([7, 0, 8]);
});
// test('TC2', () => {
//   expect(addTwoNumbers([0], [0])).toStrictEqual([0]);
// });
// test('TC3', () => {
//   expect(addTwoNumbers([9, 9, 9, 9, 9, 9, 9], [9, 9, 9, 9])).toStrictEqual([8, 9, 9, 9, 0, 0, 0, 1]);
// });
JavaScript
복사