C++-এ এককভাবে লিঙ্কযুক্ত তালিকায় বিকল্প কে নোডগুলি বিপরীত করুন

এই টিউটোরিয়ালে, আমাদেরকে N দৈর্ঘ্যের A এবং একটি পূর্ণসংখ্যা K এর একটি লিঙ্কযুক্ত তালিকা দেওয়া হয়েছে। আমাদের প্রতিটি জোড়ার আকারের সাথে K হিসাবে বিকল্প জোড়া নোডগুলিকে উল্টাতে হবে। এটিও দেওয়া হয়েছে যে N K দ্বারা বিভাজ্য। প্রথম যুক্তি হল লিঙ্ক করা তালিকা A এর হেড পয়েন্টার এবং দ্বিতীয় আর্গুমেন্ট হল একটি পূর্ণসংখ্যা K, উদাহরণস্বরূপ

ইনপুট

5 -> 6 -> 2 -> 8 -> 5 -> 2 -> 4 -> 8 -> 9 -> 6 -> null K=2

আউটপুট

6 -> 5 -> 2 -> 8 -> 2 -> 5 -> 4 -> 8 -> 6 -> 9 -> শূন্য

1 -> 2 -> 5 -> 8 -> 9 -> 6 -> 4 -> 5 -> 8 -> null K=3

আউটপুট

5 -> 2 -> 1 -> 8 -> 9 -> 6 -> 8 -> 5 -> 4 -> শূন্য

সমাধান খোঁজার পদ্ধতি

পুনরাবৃত্ত সমাধান

• প্রতি পুনরাবৃত্তি (বা লুপ) 2K নোডগুলি অতিক্রম করুন এবং জয়েন এবং টেইল পয়েন্টার ব্যবহার করে প্রদত্ত ইনপুটে (লিঙ্ক করা তালিকা) প্রতিটি জোড়া K নোডের মাথা এবং লেজ রেকর্ড করুন৷

• তারপর, লিঙ্ক করা তালিকার k নোডগুলিকে বিপরীত করুন এবং যোগদান পয়েন্টার দ্বারা নির্দেশিত প্রাথমিক লিঙ্কযুক্ত তালিকার প্রধান নোডের সাথে বিপরীত তালিকার টেল নোডে যোগ দিন৷

• তারপর আমরা বর্তমান পয়েন্টারকে পরবর্তী k নোডে পরিবর্তন করব।

• সাধারণ তালিকার লেজটি এখন শেষ নোড হিসাবে কাজ করে (যেটি নতুন লেজ দ্বারা নির্দেশিত), এবং জয়েন পয়েন্টারটি নতুন (বিপরীত) তালিকার প্রধানের দিকে নির্দেশ করবে এবং সেগুলি একত্রিত হয়েছে। সমস্ত নোড একই ধাপ অনুসরণ না করা পর্যন্ত আমরা এই পদক্ষেপগুলি পুনরাবৃত্তি করব৷

  ৷

উদাহরণ

#include নেমস্পেস ব্যবহার করে std;class Node { public:int data; নোড* পরবর্তী;};নোড* kAltReverse(struct Node* head, int k){ Node* prev =NULL; নোড* curr =head; নোড* temp =NULL; নোড* টেল =NULL; নোড* newHead =NULL; নোড* join =NULL; int t =0; যখন (curr) { t =k; join =curr; prev =NULL; যখন (curr &&t--) { temp =curr->পরবর্তী; curr->পরবর্তী =পূর্ববর্তী; prev =curr; curr =temp; } if (!newHead) newHead =prev; if (tail) tail->next =prev; tail =join; tail->next =curr; t =k; যখন (curr &&t--) { prev =curr; curr =curr-> পরবর্তী; } tail =prev; } রিটার্ন newHead;} ​​void push(Node** head_ref, int new_data){ Node* new_node =new Node(); নতুন_নোড->ডেটা =নতুন_ডেটা; new_node->next =(*head_ref); (*head_ref) =new_node;}void printList(Node* node){int count =0; যখন (নোড!=NULL) { cout <data <<" "; নোড =নোড->পরবর্তী; গণনা++; }}int main(void){ Node* head =NULL; int i; (i =6; i <27; i+=3) push(&head, i); int k =3; cout <<"প্রদত্ত লিঙ্কযুক্ত তালিকা \n"; প্রিন্টলিস্ট (মাথা); head =kAltReverse(head, k); cout <<"\n সংশোধিত লিঙ্ক তালিকা \n"; প্রিন্টলিস্ট (মাথা); রিটার্ন (0);}

আউটপুট

প্রদত্ত লিঙ্কযুক্ত তালিকা24 21 18 15 12 9 6 সংশোধিত লিঙ্কযুক্ত তালিকা18 21 24 15 12 9 6

পুনরাবৃত্ত সমাধান

• শুরু থেকে K নোডগুলিকে অতিক্রম করুন এবং k+1ম নোডে টেম্প মান সেট করুন

• সমস্ত K নোডগুলিকে উল্টে দিন।

• K নোডের সেই জোড়ার শেষ নোডের পরবর্তী পয়েন্টারটি টেম্পে সেট করুন।

• পরবর্তী পুনরাবৃত্তিটি এড়িয়ে যান যেখানে এই K নোডগুলির জোড়াকে এড়িয়ে যেতে হবে৷

  ৷

• শেষ নোড না পৌঁছানো পর্যন্ত পরবর্তী k নোডগুলিকে বিপরীত করার জন্য এই সমস্ত পদক্ষেপগুলি পুনরাবৃত্তিমূলকভাবে অনুসরণ করুন৷

ছদ্ম কোড

reverseAltK(head, k) curr =head prev =null next =null count =0 WHILE count  
উদাহরণ
 
#include নেমস্পেস ব্যবহার করে std;/* লিঙ্ক লিস্ট নোড */ক্লাস নোড{ public:int data; নোড* পরবর্তী;};/* kAltReverse() */node * _kAltReverse(node ​​*node, int k, bool b);/* বিকল্পভাবে প্রদত্ত আকারের k এর প্রদত্ত লিঙ্ক করা তালিকার গ্রুপগুলিকে বিপরীত করে। */node *kAltReverse(node ​​*head, int k){ ফেরত _kAltReverse(head, k, true);}/* kAltReverse() এর জন্য হেল্পার ফাংশন। এটি শুধুমাত্র তৃতীয় প্যারামিটার b সত্য হিসাবে পাস হলেই তালিকার k নোডগুলিকে বিপরীত করে। ,অন্যথায় পয়েন্টার k নোডগুলিকে এগিয়ে নিয়ে যায় এবং পুনরাবৃত্তভাবে নিজেকে কল করে */node * _kAltReverse(node ​​*Node, int k, bool b){ if(Node ==NULL) NULL ফেরত দেয়; int count =1; node *prev =NULL; নোড *বর্তমান =নোড; নোড *পরবর্তী; /* লুপ দুটি উদ্দেশ্য পরিবেশন করে 1) যদি b সত্য হয়, তাহলে এটি k নোডগুলিকে বিপরীত করে 2) যদি b মিথ্যা হয়, তবে এটি বর্তমান পয়েন্টারকে সরিয়ে দেয় */ while(current !=NULL &&count <=k){ next =বর্তমান->পরবর্তী; /* নোডগুলি বিপরীত করুন শুধুমাত্র যদি b সত্য হয়*/ যদি(b ==সত্য) বর্তমান->পরবর্তী =পূর্ববর্তী; prev =বর্তমান; বর্তমান =পরবর্তী; গণনা++; } /* 3) যদি b সত্য হয়, তাহলে নোড হল kth নোড। তাই নোড পরে তালিকার বাকি সংযুক্ত করুন. 4) সংযুক্ত করার পরে, নতুন হেড ফেরত দিন */ if(b ==true){ Node->next =_kAltReverse(current, k, !b); আগের রিটার্ন; } /* যদি b সত্য না হয়, তাহলে পূর্বের পরে বাকি তালিকা সংযুক্ত করুন। সুতরাং পূর্ববর্তী */ else{ prev->next =_kAltReverse(current, k, !b) এর পরে বাকি তালিকা সংযুক্ত করুন; রিটার্ন নোড; }}/* ইউটিলিটি ফাংশন *//* একটি নোড পুশ করার ফাংশন */ভয়েড পুশ(নোড** হেড_রেফ, int নিউ_ডাটা){ /* অ্যালোকেট নোড */ নোড* নিউ_নোড =নতুন নোড(); /* ডেটা রাখুন */ new_node->data =new_data; /* নতুন নোড থেকে পুরানো তালিকা লিঙ্ক করুন */ new_node->next =(*head_ref); /* নতুন নোডের দিকে নির্দেশ করতে মাথাটি সরান */ (*head_ref) =new_node;}/* লিঙ্ক করা তালিকা মুদ্রণের ফাংশন */void printList(node ​​*node){ int count =0; while(node ​​!=NULL){ cout <data <<" "; নোড =নোড->পরবর্তী; গণনা++; }}// ড্রাইভার কোডইন্ট প্রধান(অকার্যকর){ /* খালি তালিকা দিয়ে শুরু করুন */ নোড* হেড =NULL; int i; // একটি তালিকা তৈরি করুন 1->2->3->4->5...... ->20 এর জন্য(i =20; i> 0; i--) push(&head, i); cout <<"প্রদত্ত লিঙ্কযুক্ত তালিকা \n"; প্রিন্টলিস্ট (মাথা); head =kAltReverse(head, 3); cout <<"\nসংশোধিত লিঙ্ক তালিকা \n"; প্রিন্টলিস্ট (মাথা); return(0);}
 
আউটপুট
 
প্রদত্ত লিঙ্কযুক্ত তালিকা1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 সংশোধিত লিঙ্কযুক্ত তালিকা3 2 1 4 5 6 9 8 7 10 11 12 15 131214> 
উপসংহার
 

 এই টিউটোরিয়ালটি আমাদের শিখিয়েছে কিভাবে এককভাবে লিঙ্ক করা তালিকায় বিকল্প k নোডগুলিকে উল্টাতে হয় এবং c++ কোডে ছদ্ম-কোড বাস্তবায়ন করতে হয়। আমরা জাভা, পাইথন এবং অন্যান্য ভাষায় এই কোডটি লিখতে পারি। এই পদ্ধতিতে, আমরা বিকল্প K নোডগুলিকে বিপরীত করতে এবং অবশিষ্ট নোডগুলি এড়িয়ে যেতে পুনরাবৃত্তি ব্যবহার করেছি। আমরা আশা করি আপনার এই টিউটোরিয়ালটি সহায়ক হবে৷