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

この問題について思いつく 1 つのアプローチは、リストの末尾を示し、サブリストのサイズが 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 プログラムと、この問題を解決するための完全な方法 (通常) も学習しました。同じプログラムを C、Java、Python などの他の言語で書くことができます。この記事がお役に立てば幸いです。

以上がC++ を使用した指定サイズによる逆リンク リストのグループ化の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。