솔루션 개발:

질문

이 기사에서는 Leetcode의 '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.

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

질문 설명

이 질문의 등급은 보통입니다. Linked Lists를 배우기 시작한지 ​​얼마 안 된 사람이라면 말할 수 있을 것입니다. 이 질문은 정말 이상한 질문입니다. 연결된 목록이 포함된 수학 문제에 가깝습니다.

우리는 2개의 연결 리스트를 받았습니다. 두 숫자(2->4->3, 5->6->4)를 나타냅니다. 숫자를 더하고 결과를 목록으로 반환해야 합니다. 정말 하기 힘든 것 같습니다.

이 문제를 해결하려는 방법은 해당 시스템carry으로 큰 숫자를 추가하는 방법을 처음 배웠을 때로 돌아가는 것입니다. 우리는 정확한 시스템을 구현할 것입니다.

각 목록에 대한 포인터를 사용하여 정확히 동시에 목록을 살펴볼 것입니다. 그것이 우리 칼럼이 될 것입니다. 해당 열에 있는 모든 숫자를 더할 것입니다(2 + 5 = 7). 그 숫자가 9보다 크면 그 숫자를 다음 열로 옮겨야 한다는 것을 압니다. 그래서 우리가 하는 일은 {sum} - 10입니다. 다음 열로 1을 전달하는 메모와 함께. 그런 다음 이제 < 10 합계를 취하여 자체 ListNode를 생성합니다. 모든 다음 목록 노드로 이동합니다.

목록이 더 이상 남지 않고 더 많은 캐리 번호가 남을 때까지 이 작업을 반복합니다.
많은 사람들이 어린 나이에 배우는 것과 똑같은 시스템입니다.

빅오 표기법:

시간 복잡도: O(n + m) | 여기서 n/m은 우리가 순회하는 목록의 길이입니다.

공간 복잡도: O(1) | 추가 공간을 사용하지 않으며 출력을 예상대로 추가 공간으로 계산하지 않습니다.

리트코드 결과:

제출 링크 참조:

해결책

var addTwoNumbers = function (l1, l2) {

    const sentinel_node = new ListNode(0);
    let   number_carry  = 0;
    let   head          = sentinel_node;
    let   sum           = 0;

    while (l1 || l2 || sum) {

        // Add the numbers together.
        sum += (l1) ? l1.val : 0;
        sum += (l2) ? l2.val : 0;

        // Do we need a number carry?
        if (sum >= 10) {
            number_carry = 1;         // Add carry
            sum          = sum - 10;  // Update sum to 1 int
        }

        // Add new node (With our new sum)
        head.next = new ListNode(sum, null);
        head      = head.next;

        // Move both lists forward if possible
        l1 = (l1) ? l1.next : null;
        l2 = (l2) ? l2.next : null;


        // Carry the 1 if so.
        sum          = number_carry;
        number_carry = 0;
    }

    return sentinel_node.next;
};