ধরুন আমাদের একটি এককভাবে লিঙ্কযুক্ত তালিকা নোড রয়েছে যাতে পজিটিভ সংখ্যা রয়েছে। আমাদের একই লিঙ্কযুক্ত তালিকা খুঁজে বের করতে হবে যেখানে প্রতিটি নোডের পরবর্তী পয়েন্টগুলি সামনের নোড ভ্যাল নোডের দিকে নির্দেশ করে। যদি আমরা এই ধরনের নোড খুঁজে না পাই, তাহলে পরবর্তী শূন্য হবে।
সুতরাং, যদি ইনপুটটি [2,3,10,5,9] এর মত হয়, তাহলে আউটপুট হবে [2, 3, 15, ]
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
একটি অ্যারে v
সংজ্ঞায়িত করুন -
যখন নোড নাল না হয়, −
করুন-
v
-এ নোডের মান সন্নিবেশ করান -
নোড :=নোডের পাশে
-
-
ret =নতুন তালিকা নোড যার মান 0
-
temp =ret
-
i :=0
-
যখন i
-
temp এর পরের :=v[i]
মান সহ নতুন তালিকা নোড -
temp :=temp-এর পরবর্তী
-
i :=i + v[i]
-
-
রিটার্নের পরের দিকে ফিরে আসুন
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#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* solve(ListNode* node) {
vector <int> v;
while(node){
v.push_back(node->val);
node = node->next;
}
ListNode* ret = new ListNode(0);
ListNode* temp = ret;
int i = 0;
while(i < v.size()){
temp->next = new ListNode(v[i]);
temp = temp->next;
i += v[i];
}
return ret->next;
}
};
main(){
Solution ob;
vector<int> v = {2,2,3,5,9,15,3,4};
ListNode *head = make_list(v);
print_list(ob.solve(head));
} ইনপুট
{2,2,3,5,9,15,3,4} আউটপুট
[2, 3, 15, ]
