Balikkan kumpulan senarai pautan berganda mengikut saiz yang diberikan menggunakan C++

Dalam masalah ini, kita mendapat penunjuk ke kepala senarai terpaut dan integer k. Dalam kumpulan saiz k, kita perlu membalikkan senarai terpaut. Contohnya -

Input : 1 <-> 2 <-> 3 <-> 4 <-> 5 (doubly linked list), k = 3
Output : 3 <-> 2 <-> 1 <-> 5 <-> 4

Kaedah untuk mencari penyelesaian

Dalam masalah ini kita akan merumuskan algoritma rekursif untuk menyelesaikan masalah ini. Dalam kaedah ini kita akan menggunakan rekursi dan menyelesaikan masalah menggunakan rekursi.

Contoh

#include <iostream>
using namespace std;
struct Node {
   int data;
   Node *next, *prev;
};
// push function to push a node into the list
Node* push(Node* head, int data) {
   Node* new_node = new Node();
   new_node->data = data;
   new_node->next = NULL;
   Node* TMP = head;
   if (head == NULL) {
      new_node->prev = NULL;
      head = new_node;
      return head;
   }
   while (TMP->next != NULL) { // going to the last node
      TMP = TMP->next;
   }
   TMP->next = new_node;
   new_node->prev = TMP;
   return head; // return pointer to head
}
// function to print given list
void printDLL(Node* head) {
   while (head != NULL) {
   cout << head->data << " ";
   head = head->next;
}
cout << endl;
}
Node* revK(Node* head, int k) {
   if (!head)
      return NULL;
   head->prev = NULL;
   Node *TMP, *CURRENT = head, *newHead;
   int count = 0;
   while (CURRENT != NULL && count < k) { // while our count is less than k we simply reverse                                                 the nodes.
      newHead = CURRENT;
      TMP = CURRENT->prev;
      CURRENT->prev = CURRENT->next;
      CURRENT->next = TMP;
      CURRENT = CURRENT->prev;
      count++;
   }
   if (count >= k) {
      head->next = revK(CURRENT, k); // now when if the count is greater or equal
      //to k we connect first head to next head
   }
   return newHead;
}
int main() {
   Node* head;
   for (int i = 1; i <= 5; i++) {
      head = push(head, i);
   }
   cout << "Original List : ";
   printDLL(head);
   cout << "\nModified List : ";
   int k = 3;
   head = revK(head, k);
   printDLL(head);
}

Output

Original List : 1 2 3 4 5
Modified List : 3 2 1 5 4

Penjelasan kod di atas

Dalam kaedah ini, kita melingkari senarai dan mengulang sehingga kiraan kurang daripada k. Kami membuat panggilan rekursif memberikan nilai ke kepala -> seterusnya ( Di sini kami hanya membalikkan senarai semasa melintasi, tetapi apabila k dicapai, kami perlu membuat titik kepala ke elemen kth senarai lain, contohnya jika senarai kami ialah 1 2 3 4 5, k kita ialah 3, kita terbalikkan elemen tengah menjadi 3 2 1, tetapi sekarang kita perlu 1 untuk menunjuk ke 4 kerana elemen itu juga akan diterbalikkan, jadi itulah sebabnya kita menggunakan panggilan rekursif dan membuat tambahan jika kenyataan).

Kesimpulan

Dalam artikel ini, kami menyelesaikan menggunakan Rekursi. Kami juga mempelajari program C++ untuk masalah ini dan pendekatan lengkap kami untuk menyelesaikannya. Kita boleh menulis program yang sama dalam bahasa lain seperti C, java, python dan bahasa lain. Kami berharap artikel ini dapat membantu anda.

Atas ialah kandungan terperinci Balikkan kumpulan senarai pautan berganda mengikut saiz yang diberikan menggunakan C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!