C++ में लिंक्ड लिस्ट में प्लस वन - संख्या में 1 जोड़ें

समस्या विवरण

मान लीजिए हमारे पास एक गैर-ऋणात्मक पूर्णांक है जिसे गैर-खाली सिंगली लिंक्ड लिस्ट के अंकों के रूप में दर्शाया गया है, अब हमें पूर्णांक में 1 जोड़ना है। हम मान सकते हैं कि पूर्णांक में कोई अग्रणी शून्य नहीं है, सिवाय संख्या 0 के। लिंक्ड लिस्ट में सबसे महत्वपूर्ण अंक सूची के प्रमुख पर है।

उदाहरण के लिए, यदि इनपुट [1,2,3] है, तो आउटपुट [1,2,4] होगा।

समाधान दृष्टिकोण

दाएं से बाएं सबसे पहला अंक ढूंढें जो 9 नहीं है:

1. यदि head null है, तो head लौटाएं
2. curr = head, req = NULL
3. जब curr null न हो:
   • यदि curr का मान 9 नहीं है, तो req := curr
   • curr := curr का अगला
4. यदि req null है (सभी अंक 9 हैं):
   • मान 1 का एक डमी नोड बनाएं
   • डमी का अगला := head
   • जब तक head null न हो: head का मान := 0, head := head का अगला
   • डमी लौटाएं
5. अन्यथा:
   • req के मान को 1 से बढ़ाएं
   • req := req का अगला
   • जब तक req null न हो: req का मान := 0, req := req का अगला
   • head लौटाएं

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* plusOne(ListNode* head) { 
        if (!head) 
            return head; 
        ListNode* curr = head; 
        ListNode* req = NULL; 
        while (curr) { 
            if (curr->val != 9) { 
                req = curr; 
            } 
            curr = curr->next; 
        } 
        if (!req) { 
            ListNode* dummy = new ListNode(1); 
            dummy->next = head; 
            while (head) { 
                head->val = 0; 
                head = head->next; 
            } 
            return dummy; 
        } 
        else { 
            req->val++; 
            req = req->next; 
            while (req) { 
                req->val = 0; 
                req = req->next; 
            } 
            return head; 
        } 
    } 
}; 

int main(){ 
    Solution ob; 
    vector<int> v = {1,4,5}; 
    ListNode *head = make_list(v); 
    print_list(ob.plusOne(head)); 
    return 0;
}

इनपुट

{1,4,5}

आउटपुट

[1, 4, 6, ]