두 개의 음이 아닌 정수를 나타내는 비어 있지 않은 두 개의 연결 목록이 있다고 가정합니다. 여기서 가장 중요한 숫자가 먼저 오고 각 노드에는 단일 숫자가 포함됩니다. 두 숫자를 추가하고 연결 목록으로 반환해야 합니다. 따라서 목록이 [7, 2, 4, 3] + [5, 6, 4]이면 결과는 [7, 8, 0, 7]
이 됩니다.이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
dummy라는 노드를 만들고 값 0을 저장하고 스택 s1과 s2를 만듭니다.
-
s1을 l1의 노드로 채우고 s2를 s2의 노드로 채웁니다.
-
합계 :=0
-
s1이 비어 있지 않거나 s2가 비어 있지 않은 동안
-
s1이 비어 있으면 sum :=sum + s1의 최상위 값, 스택 s1에서 삭제
-
s2가 비어 있으면 sum :=sum + s2의 최상위 값, 스택 s2에서 삭제
-
더미 값 :=합계 모드 10
-
new node :=sum/10 값으로 새 노드 생성
-
새 노드의 다음:=더미
-
더미 :=새 노드
-
합계 :=합계 / 10
-
-
더미 값이 0이면 더미 다음을 반환하고, 그렇지 않으면 더미를 반환합니다.
예시(C++)
더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −
#include <bits/stdc++.h>
using namespace std;
class ListNode{
public:
int val;
ListNode *next;
ListNode(int data){
val = data;
next = NULL;
}
};
ListNode *make_list(vector<int> v){
ListNode *head = new ListNode(v[0]);
for(int i = 1; i<v.size(); i++){
ListNode *ptr = head;
while(ptr->next != NULL){
ptr = ptr->next;
}
ptr->next = new ListNode(v[i]);
}
return head;
}
void print_list(ListNode *head){
ListNode *ptr = head;
cout << "[";
while(ptr){
cout << ptr->val << ", ";
ptr = ptr->next;
}
cout << "]" << endl;
}
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* dummy;
dummy = new ListNode(0);
stack <ListNode*> s1, s2;
while(l1){
s1.push(l1);
l1 = l1->next;
}
while(l2){
s2.push(l2);
l2 = l2->next;
}
int sum = 0;
while(!s1.empty() || !s2.empty()){
if(!s1.empty()){
sum += s1.top()->val;
s1.pop();
}
if(!s2.empty()){
sum += s2.top()->val;
s2.pop();
}
dummy->val = (sum % 10);
ListNode* newNode = new ListNode(sum / 10);
newNode->next = dummy;
dummy = newNode;
sum /= 10;
}
return dummy->val == 0? dummy->next : dummy;
}
};
main(){
vector<int> v1 = {7,2,4,3};
ListNode *h1 = make_list(v1);
vector<int> v2 = {5,6,4};
ListNode *h2 = make_list(v2);
Solution ob;
print_list(ob.addTwoNumbers(h1, h2));
} 입력
[7,2,4,3] [5,6,4]
출력
[7, 8, 0, 7, ]