연결 목록: 두 개의 숫자 추가

이 게시물에서 일반적인 인터뷰 질문 중 하나인 Linked Lists에 대한 일련의 Leetcode 문제를 시작하고 싶습니다. 오늘은 Add Two Numbers Problem 을 살펴보겠습니다.

The problem is, given two non-empty linked lists representing two integers where digits are stored in reverse order, add their digits and return the sum as a linked list.

이 문제를 해결하기 위해 기본 수학의 열 방법을 사용할 것입니다. 머리부터 목록을 살펴보고 두 목록의 끝에 도달할 때까지 숫자를 한 자릿수씩 합산합니다. 길이).




마지막에 반환해야 하므로 여기서 가장 먼저 할 일은 새 목록을 만드는 것입니다.

제공된 함수 정의를 사용하여 기본적으로 값이 0인 첫 번째 노드를 만듭니다. 이것이 list라는 목록의 헤드가 될 것입니다(전체 체인을 반환하려면 항상 첫 번째 노드를 기억해야 합니다). 실제로 이 첫 번째 0을 건너뛰기 위해 다음 노드부터 목록을 반환합니다.

또한 현재 반복 내에서 작업 중인 현재 노드를 가리키기 위해 두 번째 커서 currentNode가 필요합니다. 처음에는 목록의 헤드와 같지만 목록을 수동으로 반복하는 데 사용할 것입니다.

const addTwoNumbers = (list1, list2) => {
  let list = new ListNode(0); //create a new list
  let currentNode = list; //cursor initialized to list's head
...

  return list.next; //return head's next node (to skip the first 0)
};

그런 다음 두 개의 추가 변수를 초기화해야 합니다. sum은 두 자리의 합을 보유하고 carry는 두 자리의 합이 >= 10인 경우 다음 반복에서 "이월"되는 숫자를 보유합니다.

...
  let sum = 0;
  let carry = 0;
...

};

다음으로 두 목록을 반복하고 해당 값을 합산합니다. 목록 중 하나의 끝에 도달하지 않는 한 여기에서 while 루프를 사용하여 코드를 실행합니다. 주기가 끝날 때까지 캐리 알림이 남아 있는 경우도 생각해야 하므로 이것이 세 번째로 확인할 조건입니다.

while (list1 || list2 || sum > 0) { //while list !== null or there's still reminder
...
}

루프 내에서 목록의 길이가 다른 경우를 대비하여 두 개의 명령문if이 있습니다. 각 목록의 반복에 대한 의사 코드는 다음과 같습니다.

현재 목록 노드가 여전히 존재하는지 확인하십시오(null이 아님).

해당 값을 합계에 추가합니다.

포인터 커서를 다음 노드로 이동합니다.

while (list1 || list2 || sum > 0) { //while list !== null or there's still reminder
    if (list1) { //check if list !== null in case lists have different sizes
      sum += list1.val;
      list1 = list1.next; //move the pointer
    }
    if (list2) {
      sum += list2.val;
      list2 = list2.next;
    }
...
}

한 번의 반복이 끝나면 합계 값을 갖게 됩니다.

이제 >= 10인지 확인할 차례입니다. 그렇다면(예를 들어 합계가 12인 경우) 두 번째 숫자 2만 취하고 첫 번째 숫자 1은 다음 반복으로 이월됩니다.

이 숫자를 두 자리로 나누기 위해 수학 나눗셈과 모듈로 연산을 사용합니다.

while (list1 || list2 || sum > 0) {
...
    carry = Math.floor(sum / 10);
    sum = sum % 10;
...
}

이제 출력 목록에 새 노드를 추가하고 합계 값을 제공할 수 있습니다.

다시 말하지만, 새 노드를 목록의 끝으로 푸시하여 (1) 메모리를 할당하고, (2) 현재 노드와 연결하고, (3) 값을 초기화하고, (4) 포인터를 설정합니다. 기본적으로 null입니다.

while (list1 || list2 || sum > 0) {
...
//add a new node to the list, link it with the current node, and give it the value of the sum
    currentNode.next = new ListNode(sum);
...
}

그리고 여기서 해야 할 또 하나의 작업은 currentNode 커서를 다음 반복을 위해 방금 추가한 새 노드로 이동하는 것입니다.

while (list1 || list2 || sum > 0) {
...
   //add a new node to the list, link it with the current node, and give it the value of the sum
    currentNode.next = new ListNode(sum);

  //move the cursor to the new node
    currentNode = currentNode.next;
...
}

마지막으로 다음 반복 전에 캐리어에 대한 합계를 초기화하고(다음 라운드에서 합계에 캐리어를 추가하므로) 합계를 재설정해야 합니다.

while (list1 || list2 || sum > 0) {
...
    sum = carry;
    carry = 0;
}

모두 합치자:

const addTwoNumbers = (list1, list2) => {
  let list = new ListNode(0); //create a new list
  let currentNode = list; //cursor initialized to list's head

  let sum = 0;
  let carry = 0;

  while (list1 || list2 || sum > 0) { //while list !== null or there's still reminder
    if (list1) { //check if list !== null in case lists have different sizes
      sum += list1.val;
      list1 = list1.next; //move the pointer
    }
    if (list2) {
      sum += list2.val;
      list2 = list2.next;
    }

    carry = Math.floor(sum / 10);
    sum = sum % 10;

    //add a new node to the list, link it with the current node, and give it the value of the sum
    currentNode.next = new ListNode(sum);

    //move the cursor to the new node
    currentNode = currentNode.next;

    sum = carry;
    carry = 0;
  }

  return list.next; //return head's next node (to skip the first 0)
};

끝났어!

복잡성은 어떻습니까?

이 접근 방식의 시간 복잡도는 O(n)입니다. 여기서 n은 목록을 순회해야 하므로 가장 긴 목록의 최대 노드 수입니다.
공간 복잡도: O(n) 여기서 n은 메모리에 새 목록을 생성한 이후로 가장 긴 목록의 최대 노드 수입니다.

다음 시간에는 두 가지 고급 문제에 대해 논의하겠습니다.
두 숫자 더하기 II
방법으로 두 개의 숫자 추가

도움이 되었기를 바랍니다. 추가 의견이나 질문이 있으면 알려주세요!