C++ এ একটি সাজানো সার্কুলার লিঙ্কড তালিকায় সন্নিবেশ করুন

ধরুন আমাদের কাছে একটি সার্কুলার লিঙ্কড লিস্ট থেকে একটি নোড আছে যা ক্রমবর্ধমান ক্রমে সাজানো হয়েছে, তালিকায় একটি মান insertVal সন্নিবেশ করার জন্য আমাদের একটি ফাংশন সংজ্ঞায়িত করতে হবে যাতে এটি একটি সাজানো সার্কুলার তালিকা থেকে যায়।

নোডটি তালিকার যেকোন একক নোডের একটি রেফারেন্স হতে পারে এবং এটি সার্কুলার তালিকার প্রথম মান নাও হতে পারে। সন্নিবেশের জন্য একাধিক উপযুক্ত স্থান থাকলে, আমরা নতুন মান সন্নিবেশ করার জন্য যেকোনো স্থান বেছে নিতে পারি। যদি তালিকাটি খালি থাকে, তাহলে আমাদের একটি নতুন একক সার্কুলার তালিকা তৈরি করতে হবে এবং সেই একক নোডে রেফারেন্স ফেরত দিতে হবে। অন্যথায়, আমাদের মূল প্রদত্ত নোডটি ফেরত দেওয়া উচিত।

সুতরাং, যদি ইনপুট হয় head =[3,4,1], insertVal =2, image, তাহলে আউটপুট হবে [3,4,1,2], image

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• যদি মাথা শূন্য হয়, তাহলে −

  • head :=ভ্যাল সহ নতুন নোড

  • মাথার পরের:=মাথা

• অন্যথায়

  • curr =মাথার পাশে

  • prev =মাথা

  • temp =ভ্যাল সহ নতুন নোড

  • সম্পন্ন :=মিথ্যা

  • অসীম লুপিং করুন, −

    করুন

    • যদি curr এ val>=val এবং prev এর val <=val, তাহলে −

      • পূর্ববর্তী :=টেম্পের পরবর্তী

      • temp :=curr এর পরবর্তী

      • সম্পন্ন :=সত্য

      • লুপ থেকে বেরিয়ে আসুন

    • যদি prev এর val> curr এর val, তাহলে −

      • যদি prev এর val <=val বা val <=curr এর val, তাহলে −

        • পূর্ববর্তী :=টেম্পের পরবর্তী

        • temp :=curr এর পরবর্তী

        • সম্পন্ন :=সত্য

        • লুপ থেকে বেরিয়ে আসুন

    • যদি curr মাথার সমান হয়, তাহলে -

      • লুপ থেকে বেরিয়ে আসুন

    • পূর্ববর্তী :=curr

    • curr :=curr এর পরবর্তী

  • যদি করা মিথ্যা হয়, তাহলে -

    • temp :=মাথার পাশে

    • পূর্ববর্তী :=টেম্পের পরবর্তী

    • মাথা :=তাপমাত্রা

• রিটার্ন হেড

উদাহরণ

আরো ভালোভাবে বোঝার জন্য নিচের বাস্তবায়নটি দেখি -

#include <bits/stdc++.h>
using namespace std;
class Node {
public:
   int val;
   Node* next;
   Node() {}
   Node(int _val) {
      val = _val;
      next = NULL;
   }
   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;
      }
      else{
         Node* curr = head->next;
         Node* prev = head;
         Node* temp = new Node(val);
         bool done = false;
         while(1){
            if (curr->val >= val && prev->val <= val) {
               prev->next = temp;
               temp->next = curr;
               done = true;
               break;
            }
            if (prev->val > curr->val) {
               if (prev->val <= val || val <= curr->val) {
                  prev->next = temp;
                  temp->next = curr;
                  done = true;
                  break;
               }
            }
            if (curr == head)
               break;
            prev = curr;
            curr = curr->next;
         }
         if(!done){
            temp->next = head;
            prev->next = temp;
            head = temp;
         }
      }
      return head;
   }
};
main(){
   Solution ob;
   Node *head = new Node(3);
   head->next = new Node(4);
   head->next->next = new Node(1, head);
   ob.insert(head, 2);
   Node *temp = head;
   if (head != NULL){
      do{
         cout << temp->val << " ";
         temp = temp->next;
      }
      while (temp != head);
   }
}

ইনপুট

node *head = new Node(3);
head->next = new Node(4);
head->next->next = new Node(1, head);
insertVal = 2

আউটপুট

3 4 1 2