एक संख्या का लिंक्ड लिस्ट प्रतिनिधित्व इस तरह प्रदान किया जाता है कि लिंक्ड लिस्ट के सभी नोड्स को संख्या के एक अंक के रूप में माना जाता है। नोड संख्या को इस तरह संग्रहीत करता है कि लिंक्ड लिस्ट का पहला एलिमेंट संख्या का सबसे महत्वपूर्ण अंक (most significant digit) रखता है, और लिंक्ड लिस्ट का अंतिम एलिमेंट सबसे कम महत्वपूर्ण बिट (least significant bit) रखता है। उदाहरण के लिए, संख्या 202345 को लिंक्ड लिस्ट में (2->0->2->3->4->5) के रूप में दर्शाया गया है।
और इस लिंक्ड लिस्ट द्वारा दर्शाई गई संख्या में 1 जोड़ने के लिए हमें लिस्ट के सबसे कम महत्वपूर्ण बिट के मान की जांच करनी होगी। यदि यह 9 से कम है तो ठीक है अन्यथा कोड अगले अंक को बदलेगा और इसी तरह आगे।
आइए एक उदाहरण देखें कि इसे कैसे करना है, 1999 को (1->9->9->9) के रूप में दर्शाया गया है और इसमें 1 जोड़ने पर यह (2->0->0->0) में बदल जाना चाहिए।
Input:1999 Output:2000
व्याख्या
लिंक्ड लिस्ट के रूप में दर्शाई गई दी गई संख्या में 1 जोड़ने के लिए कुछ चरणों का पालन करना होगा, जो हैं:
लिंक्ड लिस्ट को उलटना: आपको लिंक्ड लिस्ट को उलटना होगा जिसका अर्थ है अंतिम अंक को पहले और पहले को अंतिम में बदलना। उदाहरण के लिए, 1->9->9->9, 9->9->9->1 में बदल जाता है।
इस बदली हुई लिंक्ड लिस्ट के लिए अब लिस्ट को पार करें, बाएं-most नोड में 1 जोड़ें। यदि इस नोड का मान 9 के बराबर है तो अगले नोड में कैरी प्रचारित करें। वही प्रक्रिया तब तक करें जब तक कैरी मौजूद है।
स्ट्रिंग को मूल रूप में वापस उलटें और फिर प्रिंट करने के लिए हेड लौटाएं।
उदाहरण
#include <iostream>
using namespace std;
//n=अगला नोड ; d=डेटा ; p= पिछला नोड; h=हेड नोड; c=वर्तमान नोड
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<
