Pengumpulan senarai terpaut terbalik mengikut saiz yang diberikan menggunakan C++

Dalam artikel ini, kami berurusan dengan senarai pautan tunggal dan tugasnya adalah untuk membalikkan senarai dalam kumpulan k. Contohnya -

Input: 1->2->3->4->5->6->7->8->NULL, K = 3
Output: 3->2->1->6->5->4->8->7->NULL

Input: 1->2->3->4->5->6->7->8->NULL, K = 5
Output: 5->4->3->2->1->8

Untuk masalah ini, satu pendekatan yang terlintas di fikiran ialah mengekori senarai dan membalikkan senarai apabila saiz subsenarai mencapai k dan teruskan.

Kaedah untuk mencari penyelesaian

Dengan kaedah ini, kami biasanya mengulangi senarai dan menyimpan pembilang untuk mengira bilangan elemen dalam subsenarai. Apabila kaunter mencapai kiraan k, kita terbalikkan bahagian itu.

Contoh

#include <bits/stdc++.h>
using namespace std;
class Node {
   public:
   int data;
   Node* next;
};
Node* reverse(Node* head, int k) {
   if (!head)
      return NULL;
   Node* curr = head;
   Node* next = NULL;
   Node* prev = NULL;
   int count = 0;
   while (curr != NULL && count < k) { // we reverse the list till our count is less than k
      next = curr->next;
      curr->next = prev;
      prev = curr;
      curr = next;
      count++;
   }
   if (next != NULL) // if our link list has not ended we call reverse function again
      head->next = reverse(next, k);
   return prev;
}
void push(Node** head_ref, int new_data) { // function for pushing data in the list
   Node* new_node = new Node();
   new_node->data = new_data;
   new_node->next = (*head_ref);
   (*head_ref) = new_node;
}
void printList(Node* node) { // function to print linked list

   while (node != NULL) {
      cout << node->data << " ";
      node = node->next;
   }
   cout << "\n";
}
int main() {
   Node* head = NULL;

   int k = 3; // the given k

   push(&head, 8);
   push(&head, 7);
   push(&head, 6);
   push(&head, 5);
   push(&head, 4);
   push(&head, 3);
   push(&head, 2);
   push(&head, 1);

   cout << "Original list \n";
   printList(head);

   head = reverse(head, k); // this function will return us our new head
   cout << "New list \n";
   printList(head);
   return (0);
}

Output

Original list
1 2 3 4 5 6 7 8
New list
3 2 1 6 5 4 8 7

Kerumitan masa kaedah di atas ialah O(N), di mana N ialah saiz senarai yang diberikan dan kaedah itu sesuai untuk rekursi. Pendekatan ini juga berfungsi untuk kekangan yang lebih tinggi.

Penjelasan kod di atas

Dalam kaedah ini, kita akan lelaran melalui tatasusunan dan terus membalikkannya sehingga pembolehubah pembilang kita kurang daripada k. Apabila pembilang mencapai nilai k, kami memanggil fungsi penyongsangan lain untuk menyambungkan nod terakhir subsenarai ini ke nod pertama subsenarai songsang seterusnya. Ini dilakukan secara rekursif.

Kesimpulan

Dalam artikel ini, kami menyelesaikan masalah membalikkan senarai terpaut mengikut kumpulan saiz tertentu menggunakan rekursi. Kami juga mempelajari program C++ untuk menyelesaikan masalah ini dan kaedah lengkap untuk menyelesaikan masalah ini (Normal). 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 Pengumpulan senarai terpaut terbalik mengikut saiz yang diberikan menggunakan C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!