C++の単一リンクリスト内の代替Kノードを逆にする

このチュートリアルでは、長さNで整数KのリンクリストAが与えられます。各ペアのサイズがKであるノードの交互のペアを逆にする必要があります。また、NはKで割り切れることが与えられます。最初の引数はリンクリストAのヘッドポインタと2番目の引数は整数Kです。たとえば

入力

5 -> 6 -> 2 -> 8 -> 5 -> 2 -> 4 -> 8 -> 9 -> 6 -> null K=2

出力

6 -> 5 -> 2 -> 8 -> 2 -> 5 -> 4 -> 8 -> 6 -> 9 -> null

1 -> 2 -> 5 -> 8 -> 9 -> 6 -> 4 -> 5 -> 8 -> null K=3

出力

5 -> 2 -> 1 -> 8 -> 9 -> 6 -> 8 -> 5 -> 4 -> null

解決策を見つけるためのアプローチ

反復ソリューション

• 反復（またはループ）ごとに2Kノードをトラバースし、結合およびテールポインターを使用して、指定された入力（リンクリスト）にKノードの各ペアのヘッドとテールを記録します。

• 次に、リンクリストのkノードを逆にして、逆リストのテールノードを、結合ポインタが指す最初のリンクリストのヘッドノードと結合します。

• 次に、現在のポインタを次のkノードに変更します。

• 通常のリストのテールが最後のノード（新しいテールが指す）として機能し、結合ポインターが新しい（反転した）リストの先頭を指し、それらがマージされます。すべてのノードが同じ手順に従うまで、これらの手順を繰り返します。

例

#include <bits/stdc++.h>
using namespace std;
class Node {
   public:
   int data;
   Node* next;
};
Node* kAltReverse(struct Node* head, int k){
   Node* prev = NULL;
   Node* curr = head;
   Node* temp = NULL;
   Node* tail = NULL;
   Node* newHead = NULL;
   Node* join = NULL;
   int t = 0;
   while (curr) {
      t = k;
      join = curr;
      prev = NULL;
      while (curr && t--) {
         temp = curr->next;
         curr->next = prev;
         prev = curr;
         curr = temp;
      }
      if (!newHead)
         newHead = prev;
      if (tail)
         tail->next = prev;
      tail = join;
      tail->next = curr;
      t = k;
      while (curr && t--) {
         prev = curr;
         curr = curr->next;
      }
      tail = prev;
   }
   return newHead;
}
void push(Node** head_ref, int new_data){
   Node* new_node = new Node();
   new_node->data = new_data;
   new_node->next = (*head_ref);
   (*head_ref) = new_node;
}
void printList(Node* node){
   int count = 0;
   while (node != NULL) {
      cout << node->data << " ";
      node = node->next;
      count++;
   }
}
int main(void){
   Node* head = NULL;
   int i;
   for (i = 6; i <27; i+=3)
      push(&head, i);
   int k = 3;
   cout << "Given linked list \n";
   printList(head);
   head = kAltReverse(head, k);
   cout << "\n Modified Linked list \n";
   printList(head);
   return (0);
}

出力

Given linked list
24 21 18 15 12 9 6
Modified Linked list
18 21 24 15 12 9 6

再帰的ソリューション

• 開始からKノードをトラバースし、一時値をk+1番目のノードに設定します

• 通過したすべてのKノードを逆にします。

• Kノードのそのペアの最後のノードの次のポインタをtempに設定します。

• それらのKノードのペアがスキップする必要がある次の反復をスキップします。

• 最後のノードに到達するまで、次のkノードを逆にするために、これらすべての手順を再帰的に実行します。

擬似コード

reverseAltK(head, k)
   curr = head
   prev = null
   next = null
   count = 0
   WHILE count < k AND curr
      next = curr.next
      curr.next = prev
      prev = curr
      curr = next
      count = count + 1
IF head
   head.next = curr
count = 0
WHILE count < k-1 AND curr
   curr = curr.next
   count = count + 1
IF curr
   curr.next = reverseKGroupAltRecursive(curr.next, k)
return prev

例

#include <bits/stdc++.h>
using namespace std;
/* Link list node */
class node{
   public:
   int data;
   node* next;
};
/* Helper function for kAltReverse() */
node * _kAltReverse(node *node, int k, bool b);

/* Alternatively reverses the given linked list
in groups of given size k. */
node *kAltReverse(node *head, int k){
   return _kAltReverse(head, k, true);
}
/* Helper function for kAltReverse().
It reverses k nodes of the list only if
the third parameter b is passed as true,
otherwise moves the pointer k nodes ahead
and recursively calls iteself */
node * _kAltReverse(node *Node, int k, bool b){
   if(Node == NULL)
      return NULL;
   int count = 1;
   node *prev = NULL;
   node *current = Node;
   node *next;
   /* The loop serves two purposes
      1) If b is true,
      then it reverses the k nodes
      2) If b is false,
      then it moves the current pointer */
   while(current != NULL && count <= k){
      next = current->next;
      /* Reverse the nodes only if b is true*/
         if(b == true)
            current->next = prev;
      prev = current;
      current = next;
      count++;
   }
   /* 3) If b is true, then node is the kth node.
   So attach rest of the list after node.
   4) After attaching, return the new head */
   if(b == true){
      Node->next = _kAltReverse(current, k, !b);
      return prev;
   }
   /* If b is not true, then attach
   rest of the list after prev.
   So attach rest of the list after prev */
   else{
      prev->next = _kAltReverse(current, k, !b);
      return Node;
   }
}
/* UTILITY FUNCTIONS */
/* Function to push a node */
void push(node** head_ref, int new_data){
   /* allocate node */
   node* new_node = new node();
   /* put in the data */
   new_node->data = new_data;
   /* link the old list off the new node */
   new_node->next = (*head_ref);
   /* move the head to point to the new node */
   (*head_ref) = new_node;
}
/* Function to print linked list */
void printList(node *node){
   int count = 0;
   while(node != NULL){
      cout << node->data << " ";
      node = node->next;
      count++;
   }
}
// Driver Code
int main(void){
   /* Start with the empty list */
   node* head = NULL;
   int i;
   // create a list 1->2->3->4->5...... ->20
   for(i = 20; i > 0; i--)
      push(&head, i);
   cout << "Given linked list \n";
   printList(head);
   head = kAltReverse(head, 3);
   cout << "\nModified Linked list \n";
   printList(head);
   return(0);
}

出力

Given linked list
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Modified Linked list
3 2 1 4 5 6 9 8 7 10 11 12 15 14 13 16 17 18 20 19

結論

このチュートリアルでは、単一リンクリストの代替kノードとc++コードの擬似コード実装を逆にする方法を学びました。このコードは、Java、Python、およびその他の言語で作成することもできます。このアプローチでは、再帰を使用して代替Kノードを逆にし、残りのノードをスキップしました。このチュートリアルがお役に立てば幸いです。