सी++ में पुन:क्रमित सूची

मान लीजिए हमारे पास l1 -> l2 -> l3 -> l4 -> … -> l(n-1) -> ln जैसी एक लिंक की गई सूची है। हमें इस सूची को l1 -> ln -> l2 -> l(n - 1) -> … और इसी तरह के रूप में पुनर्व्यवस्थित करना है। यहां बाधा यह है कि, हम सूची नोड्स में मानों को संशोधित नहीं कर सकते हैं, केवल नोड को ही बदला जा सकता है। उदाहरण के लिए, यदि सूची [1,2,3,4,5] जैसी है, तो आउटपुट [1,5,2,4,3]

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• रिवर्स ऑपरेशन करने के लिए रिवर्स नामक एक विधि को परिभाषित करें। यह नोड हेड और नोड को पीछे ले जाएगा। यह नीचे की तरह काम करेगा -

• अगर सिर खाली है, तो पिछला वापस आएं

• अस्थायी:=सिर के आगे

• सिर के आगे :=पिछला, और पिछला :=सिर

• रिवर्स रिवर्स (अस्थायी, पिछला)

• पुन:क्रमित करने का कार्य नीचे जैसा होगा -

• यदि सिर शून्य है, तो शून्य वापस लौटें

• धीमी और तेज़ नामक दो नोड पॉइंटर्स को परिभाषित करें, और उन्हें सिर से प्रारंभ करें

• जबकि उपवास और अगले उपवास दोनों शून्य नहीं हैं,

  • धीमा :=धीमे के आगे

  • उपवास :=उपवास के अगले के बाद

• तेज़:=उल्टा (धीमे के आगे)

• धीमी के आगे शून्य और धीमी के रूप में सेट करें:=सिर

• दो सूची नोड पॉइंटर्स temp1 और temp2 परिभाषित करें

• जबकि उपवास शून्य नहीं है

  • temp1 :=धीमी के आगे, temp2 :=तेज के आगे

  • धीमी गति के आगे:=तेज, तेज के बाद:=temp1

  • धीमा:=अस्थायी 1, तेज़:=अस्थायी 2

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#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* successor = NULL;
   ListNode* reverse(ListNode* head, ListNode* prev = NULL){
      if(!head)return prev;
      ListNode* temp = head->next;
      head->next = prev;
      prev = head;
      return reverse(temp, prev);
   }
   void reorderList(ListNode* head) {
      if(!head)return;
      ListNode* slow = head;
      ListNode* fast = head;
      while(fast && fast->next){
         slow = slow->next;
         fast = fast->next->next;
      }
      fast = reverse(slow->next);
      slow->next = NULL;
      slow = head;
      ListNode *temp1, *temp2;
      while(fast){
         temp1 = slow->next;
         temp2 = fast->next;
         slow->next = fast;
         fast->next = temp1;
         slow = temp1;
         fast = temp2;
      }
   }
};
main(){
   vector<int> v = {1,2,3,4,5};
   ListNode *h1 = make_list(v);
   Solution ob;
   (ob.reorderList(h1));
   print_list(h1);
}

इनपुट

[1,2,3,4,5]

आउटपुट

[1, 5, 2, 4, 3, ]