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 ++プログラムと、この問題を解決するための完全なアプローチ（Normal）についても学びました。同じプログラムを、C、java、python、その他の言語などの他の言語で作成できます。この記事がお役に立てば幸いです。