C++-এ Plus One Linked List: লিংকড লিস্ট দিয়ে প্রকাশিত সংখ্যার সাথে ১ যোগ করা

একটি নন-নেগেটিভ ইন্টিজার একটি সিংলি লিংকড লিস্ট হিসেবে প্রকাশ করা হয়েছে, যেখানে সবচেয়ে গুরুত্বপূর্ণ ডিজিট (most significant digit) হেডে রয়েছে। এই লিস্টকে মডিফাই না করে (বা করে) সংখ্যাটির সাথে ১ যোগ করে ফলাফল লিংকড লিস্ট হিসেবে রিটার্ন করতে হবে।

উদাহরণ

ইনপুট: [1,2,3] → আউটপুট: [1,2,4]

ইনপুট: [9,9,9] → আউটপুট: [1,0,0,0] (নতুন হেড তৈরি হয়)

সমাধানের পদ্ধতি

1. যদি হেড নাল হয়, তবে হেড রিটার্ন করুন।
2. লিস্ট ট্রাভার্স করে সবচেয়ে ডানে থাকা নন-৯ ডিজিট খুঁজে বের করুন (এটিকে req বলা হয়েছে)।
3. যদি কোনো নন-৯ ডিজিট না পাওয়া যায় (সব ৯ হয়):
   • ভ্যালু ১ দিয়ে একটি নতুন ডামি নোড তৈরি করুন।
   • এর নেক্সটকে পুরনো হেড করে দিন।
   • পুরনো লিস্টের সব নোডের ভ্যালু ০ করে দিন।
   • ডামি নোড রিটার্ন করুন।
4. অন্যথায়:
   • req নোডের ভ্যালু ১ বাড়ান।
   • req এর পরের সব নোডের ভ্যালু ০ করে দিন।
   • পুরনো হেড রিটার্ন করুন।

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, ]