একটি সংখ্যার লিঙ্কযুক্ত তালিকা উপস্থাপনা এমনভাবে প্রদান করা হয় যাতে লিঙ্ক করা তালিকার সমস্ত নোডকে সংখ্যার এক সংখ্যা হিসাবে গণ্য করা হয়। নোড সংখ্যাটিকে এমনভাবে সঞ্চয় করে যে লিঙ্ক করা তালিকার প্রথম উপাদানটি সংখ্যাটির সবচেয়ে উল্লেখযোগ্য সংখ্যা ধারণ করে, এবং লিঙ্কযুক্ত তালিকার শেষ উপাদানটি সংখ্যার সবচেয়ে কম গুরুত্বপূর্ণ বিট ধারণ করে। উদাহরণস্বরূপ, 202345 নম্বরটি লিঙ্কযুক্ত তালিকায় (2->0->2->3->4->5) হিসাবে উপস্থাপন করা হয়েছে।
এবং এই লিঙ্কযুক্ত তালিকায় একটি যোগ করার জন্য প্রতিনিধিত্ব করা সংখ্যা আমাদের তালিকার সর্বনিম্ন উল্লেখযোগ্য বিটের মান পরীক্ষা করতে হবে। যদি এটি 9 এর থেকে কম হয় তবে এটি ঠিক আছে অন্যথায় কোডটি পরবর্তী সংখ্যা পরিবর্তন করবে এবং আরও অনেক কিছু।
এখন এটি কীভাবে করবেন তা জানার জন্য একটি উদাহরণ দেখা যাক, 1999 কে (1-> 9-> 9 -> 9) হিসাবে উপস্থাপন করা হয়েছে এবং এটিতে 1 যোগ করলে এটি (2->0->0->0)<এ পরিবর্তন করা উচিত। /P>
Input:1999 Output:2000
ব্যাখ্যা
একটি লিঙ্ক তালিকা হিসাবে উপস্থাপিত একটি প্রদত্ত সংখ্যার সাথে 1 যোগ করার অর্থ হল কিছু পদক্ষেপ অনুসরণ করা,
- লিঙ্ক করা তালিকাটিকে উল্টানো:আপনাকে লিঙ্ক করা তালিকাটি উল্টাতে হবে যার অর্থ শেষ সংখ্যাটি প্রথম এবং প্রথম থেকে শেষ পরিবর্তন করা। উদাহরণস্বরূপ, 1-> 9-> 9 -> 9 রূপান্তরিত হয় 9-> 9 -> 9 ->1।
- এই পরিবর্তিত লিঙ্ক তালিকার জন্য এখন তালিকাটি অতিক্রম করুন, বাম-সবচেয়ে নোডে একটি যোগ করুন। যদি এই নোডের মান 9 এর সমান হয় তবে পরবর্তী নোডে একটি বহন প্রচার করুন। বহন না হওয়া পর্যন্ত একই পদ্ধতি করুন।
- স্ট্রিংটিকে আসল আকারে ফিরিয়ে দিন এবং তারপরে স্ট্রিং প্রিন্ট করার জন্য মাথাটি ফিরিয়ে দিন।
উদাহরণ
#include <iostream>
using namespace std;
//n=next node ; d=data ; p= previous node; h=head node; c=current node
class Node {
public:
int d;
Node* n;
};
Node *newNode(int d) {
Node *new_node = new Node;
new_node->d = d;
new_node->n = NULL;
return new_node;
}
Node *reverse(Node *h) {
Node * p = NULL;
Node * c = h;
Node * n;
while (c != NULL) {
n = c->n;
c->n = p;
p = c;
c = n;
}
return p;
}
Node *addOneUtil(Node *h) {
Node* res = h;
Node *temp, *p = NULL;
int carry = 1, sum;
while (h != NULL) {
sum = carry + h->d;
carry = (sum >= 10)? 1 : 0;
sum = sum % 10;
h->d = sum;
temp = h;
h = h->n;
}
if (carry > 0)
temp->n = newNode(carry);
return res;
}
Node* addOne(Node *h) {
h = reverse(h);
h = addOneUtil(h);
return reverse(h);
}
int main() {
Node *h = newNode(1);
h->n = newNode(9);
h->n->n = newNode(9);
h->n->n->n = newNode(9);
h = addOne(h);
while (h != NULL) {
cout << h->d;
h = h->n;
}
cout<<endl;
return 0;
} 