使用C++按給定大小將鍊錶分組反轉

在本文中，我們處理一個單鍊錶，任務是以 k 為一組反轉該清單。例如 -

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

對於這個問題，想到的一種方法是尾隨列表並在子列表的大小達到 k 並繼續時反轉列表。

尋找解決方案的方法

透過這種方法，我們通常會遍歷列表並保留一個計數器來計算子列表中的元素數量。當計數器達到 k 的計數時，我們反轉該部分。

範例

#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);
}

輸出

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

上述方法的時間複雜度為O(N)，其中N是給定清單的大小，並且此方法適用於遞迴。這種方法也適用於更高的約束。

上述程式碼的解釋

我們將在這個方法中遍歷陣列並不斷反轉它，直到我們的計數器變數小於 k 。當計數器達到 k 的值時，我們呼叫另一個反轉函數將該子清單的最後一個節點連接到下一個反轉子清單的第一個節點。這是透過遞歸完成的。

結論

在本文中，我們解決了使用遞歸按給定大小的群組反轉鍊錶的問題。我們也學習了解決此問題的 C 程序以及解決此問題的完整方法（Normal）。我們可以用其他語言像是C、java、python等語言來寫同樣的程式。我們希望這篇文章對您有幫助。

以上是使用C++按給定大小將鍊錶分組反轉的詳細內容。更多資訊請關注PHP中文網其他相關文章！