ধরুন আমাদের দুটি অ-খালি লিঙ্কযুক্ত তালিকা রয়েছে যা দুটি অ-ঋণাত্মক পূর্ণসংখ্যার প্রতিনিধিত্ব করে। এখানে সবচেয়ে উল্লেখযোগ্য সংখ্যাটি প্রথমে আসে এবং তাদের প্রতিটি নোডে একটি একক সংখ্যা থাকে। আমরা দুটি সংখ্যা adf এবং একটি লিঙ্ক তালিকা হিসাবে এটি ফেরত আছে. তাই যদি তালিকা হয় [7, 2, 4, 3] + [5, 6, 4], তাহলে ফলাফল হবে [7, 8, 0, 7]
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
ডামি নামে একটি নোড তৈরি করুন এবং মান 0 সংরক্ষণ করুন, স্ট্যাকগুলি s1 এবং s2 তৈরি করুন৷
-
l1 এর নোড দ্বারা s1 এবং 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, ]
