किसी संख्या की लिंक की गई सूची का प्रतिनिधित्व इस तरह से प्रदान किया जाता है कि लिंक की गई सूची के सभी नोड्स को संख्या के एक अंक के रूप में माना जाता है। नोड संख्या को इस तरह संग्रहीत करता है कि लिंक की गई सूची का पहला तत्व संख्या का सबसे महत्वपूर्ण अंक रखता है, और लिंक की गई सूची का अंतिम तत्व संख्या का सबसे कम महत्वपूर्ण बिट रखता है। उदाहरण के लिए, संख्या 202345 को लिंक की गई सूची में (2->0->2->3->4->5) के रूप में दर्शाया गया है।
और इस लिंक की गई सूची में एक प्रतिनिधित्व संख्या जोड़ने के लिए हमें सूची के कम से कम महत्वपूर्ण बिट के मूल्य की जांच करनी होगी। यदि यह 9 से कम है तो ठीक है अन्यथा कोड अगले अंक को बदल देगा और इसी तरह।
अब इसे कैसे करना है, यह जानने के लिए एक उदाहरण देखते हैं, 1999 को (1-> 9-> 9 -> 9) के रूप में दर्शाया गया है और इसमें 1 जोड़ने से इसे (2->0->0->0)<में बदलना चाहिए। /पी>
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;
}