C++-এ লিংকড লিস্ট জাম্প (Linked List Jumps) প্রোগ্রাম

সমস্যা বিবরণ

একটি সিঙ্গলি লিংকড লিস্ট দেওয়া থাকলে (পজেটিভ ভ্যালু), প্রতিটি নোডের next পয়েন্টারকে এর ভ্যালুয়ের মানত নিজের থেকে আগে যাওয়া নোডে পয়েন্ট করান। যদি এমন নোড নেই, তবে NULL।

উদাহরণ: [2,2,3,5,9,15,3,4] → ইন্ডেক্স ০ (ভ্যালু ২) → ইন্ডেক্স ২ (ভ্যালু ৩) → ইন্ডেক্স ৫ (ভ্যালু ১৫) → শেষ। ফলাফল: [2, 3, 15]

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

1. লিংকড লিস্টকে ভেক্টরে কনভার্ট করুন।
2. নতুন লিস্ট বানান: i = 0 থেকে শুরু করে i += v[i] করে যান।
3. প্রতিটি ভিজিট করা নোড নতুন লিস্টে যোগ করুন।

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 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 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;
    }
};

int main() {
    Solution ob;
    vector v = {2, 2, 3, 5, 9, 15, 3, 4};
    ListNode* head = make_list(v);
    print_list(ob.solve(head));
    return 0;
}

আউটপুট

[2, 3, 15, ]

জটিলতা

• সময়: O(n)
• স্থান: O(n)