[LeetCode] 2. Add Two Numbers (C++)

[LeetCode] 2. Add Two Numbers (C++)

반응형

Question 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.

Example 1:

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

Example 2:

Input: l1 = [0], l2 = [0] Output: [0]

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]

Constraints:

The number of nodes in each linked list is in the range [1, 100].

[1, 100]. 0 <= Node.val <= 9

It is guaranteed that the list represents a number that does not have leading zeros.

Solution)

해당 문제는 너무 간단하고 단순하게 풀 생각으로 시도했다가 실패했던 문제이다.

처음에는 순수하게 입력데이터 값들을 string 값으로 받아 atoi 또는 atol 함수를 이용하여 숫자로 변형 한 뒤 합을 계산하였다.

여기서 간과했던 것은

The number of nodes in each linked list is in the range [1, 100].

이 부분이었는데 100자리 숫자는 Integer와 long long 타입으로도 커버가 되지 않는다.

이에 따라

입력 데이터 ListNode l1, l2 값 들을 하나하나 다 더해가며 next Node를 탐색해야 한다.

-> l1, 또는 l2의 next 노드가 존재하지 않을 때 까지

또 여기서 핵심은 Value값이 10이 넘었을 때 그 next노드 Value값에 +1을 해야 했는데 나는 flag값을 이용하여 이를 처리하였다.

class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode* head = new ListNode(); // head 노드 설정 ListNode* node = head; // ListNode의 head 노드 설정 int plus = 0; // 10이 넘었을 때 +1의 Flag while(l1 != nullptr || l2 != nullptr){ // 두개 다 모두 nullptr이 아닐 때 (next값이 존재 할 때 ) int sum = plus; if(l1 != nullptr) { sum += l1 -> val; } if(l2 != nullptr) { sum += l2 -> val; } if(sum > 9){ sum = sum % 10; plus = 1; } else { plus = 0; } ListNode* insert = new ListNode(sum); node -> next = insert; node = node->next; l1 = l1 == nullptr ? nullptr : l1->next; l2 = l2 == nullptr ? nullptr : l2->next; if(plus == 1) { node -> next = new ListNode(plus); // 10이 넘어가면 그 다음 노드값에 value가 1인 노드를 생성한다. } } return head->next; } };

끝.

P.S) 아직까지는 Runtime과 Memory를 생각하지 않고 있는데 다시 C++가 적응되면 그 때는 해당 값들을 신경써야겠다..

반응형

from http://erjuer.tistory.com/95 by ccl(A) rewrite - 2021-12-06 01:27:08