একটি সংখ্যার লিংকড লিস্ট রিপ্রেজেন্টেশন এমনভাবে দেওয়া হয় যে লিংকড লিস্টের সব নোড সংখ্যার একটি ডিজিট হিসেবে বিবেচিত হয়। নোডটি সংখ্যাটি এমনভাবে স্টোর করে যে লিংকড লিস্টের প্রথম এলিমেন্টে সংখ্যার সবচেয়ে গুরুত্বপূর্ণ ডিজিট (most significant digit) থাকে, এবং শেষ এলিমেন্টে সবচেয়ে কম গুরুত্বপূর্ণ বিট (least significant bit) থাকে। উদাহরণস্বরূপ, ২০২৩৪৫ সংখ্যাটি লিংকড লিস্টে (2->0->2->3->4->5) হিসেবে প্রকাশিত হয়।
এই লিংকড লিস্ট রিপ্রেজেন্টেড সংখ্যাতে ১ যোগ করতে হলে আমাদের লিস্টের least significant bit-এর মান চেক করতে হবে। যদি সেটি ৯-র চেয়ে ছোট হয় তবে ঠিক আছে, অন্যথায় কোডটি পরবর্তী ডিজিট পরিবর্তন করবে এবং এভাবেই চলতে থাকবে।
এখন একটি উদাহরণ দিয়ে দেখি কিভাবে করা যায়, ১৯৯৯কে (1-> 9-> 9 -> 9) হিসেবে প্রকাশ করা হয়েছে এবং এতে ১ যোগ করলে সেটি (2->0->0->0) হবে।
Input:1999 Output:2000
ব্যাখ্যা
লিংকড লিস্ট রিপ্রেজেন্টেড সংখ্যাতে ১ যোগ করার জন্য কিছু ধাপ অনুসরণ করতে হয়:
লিংকড লিস্ট রিভার্স করা: লিংকড লিস্টটি রিভার্স করতে হবে অর্থাৎ শেষ ডিজিটকে প্রথমে এবং প্রথমকে শেষে আনা। উদাহরণস্বরূপ, 1-> 9-> 9 -> 9 কনভার্ট হবে 9-> 9 -> 9 ->1।
এই পরিবর্তিত লিংকড লিস্ট ট্রাভার্স করুন, বামপাশের নোডে ১ যোগ করুন। যদি এই নোডের মান ৯-এর সমান হয়, তবে পরবর্তী নোডে ক্যারি প্রপাগেট করুন। ক্যারি থাকা পর্যন্ত একই প্রসেস চালিয়ে যান।
লিস্টটিকে আবার মূল রূপে রিভার্স করুন এবং হেড রিটার্ন করুন যাতে প্রিন্ট করা যায়।
উদাহরণ
#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; }
