সর্টেড সার্কুলার লিংকড লিস্টে ইনসারশন C++-এ

সমস্যা বিবরণ

একটি সর্টেড সার্কুলার লিংকড লিস্টের একটি নোড রেফারেন্স দেওয়া আছে (যেটি হেড নাও হতে পারে)। একটি ভ্যালু insertVal লিস্টে ইনসার্ট করতে হবে যাতে লিস্ট সর্টেড সার্কুলার থাকে। যদি লিস্ট খালি হয়, তবে নতুন নোডটি নিজে নিজের পয়েন্ট করবে এবং সেটি রিটার্ন করুন। একাধিক উপযুক্ত জায়গা থাকলে যেকোনো একটি ব্যবহার করুন।

উদাহরণ

হেড = [3,4,1] (সার্কুলার), insertVal = 2

আউটপুট: [3,4,1,2] (সার্কুলার)

অ্যালগরিদম

1. যদি হেড নাল হয়: নতুন নোড বানিয়ে এর next = head করুন এবং রিটার্ন করুন।
2. দুটি পয়েন্টার prev = head, curr = head->next।
3. নতুন নোড temp তৈরি করুন।
4. লুপ চালান (সার্কুলার, তাই curr == head হলে ব্রেক):
   • কেস ১ (নরমাল ইনসারশন): prev->val <= val <= curr->val হলে prev->next = temp; temp->next = curr; করে ব্রেক।
   • কেস ২ (ওয়্র্যাপ-অরাউন্ড): prev->val > curr->val হলে (লিস্টের এন্ড-স্টার্ট বাউন্ডারি), যদি val >= prev->val বা val <= curr->val হয়, তবে সেখানে ইনসার্ট করুন।
   • prev = curr; curr = curr->next;
5. যদি লুপ শেষ হওয়ার পরেও ইনসার্ট না হয় (সব নোড একই ভ্যালু), তবে হেডের আগে ইনসার্ট করুন।

C++ বাস্তবায়ন

#include <bits/stdc++.h>
using namespace std;

class Node {
public:
    int val;
    Node* next;
    Node() : val(0), next(nullptr) {}
    Node(int _val) : val(_val), next(nullptr) {}
    Node(int _val, Node* _next) : val(_val), next(_next) {}
};

class Solution {
public:
    Node* insert(Node* head, int val) {
        if (!head) {
            head = new Node(val);
            head->next = head;
            return head;
        }
        Node* prev = head;
        Node* curr = head->next;
        Node* temp = new Node(val);
        bool done = false;

        while (true) {
            if (prev->val <= val && val <= curr->val) {
                prev->next = temp;
                temp->next = curr;
                done = true;
                break;
            }
            if (prev->val > curr->val) { // wrap-around point
                if (val >= prev->val || val <= curr->val) {
                    prev->next = temp;
                    temp->next = curr;
                    done = true;
                    break;
                }
            }
            prev = curr;
            curr = curr->next;
            if (curr == head) break;
        }
        if (!done) {
            temp->next = head;
            prev->next = temp;
            head = temp; // অপশনাল: নতুন হেড রিটার্ন
        }
        return head;
    }
};

int main() {
    // টেস্ট করুন
    return 0;
}

ইনপুট ও আউটপুট

জটিলতা বিশ্লেষণ

• সময় জটিলতা: O(N) — N = নোড সংখ্যা।
• স্থান জটিলতা: O(1) — কনস্ট্যান্ট এক্সট্রা স্পেস।