C++の単一リンクリスト内の交互の奇数ノードと偶数ノード

単一のリンクリストは、2つの部分を含む線形データ構造です。1つはデータで、もう1つはリスト内の次の要素へのポインタです。

代替の奇数および偶数の単一リンクリスト は、一方のノードに偶数のデータがあり、もう一方のノードに奇数のデータメンバーがあるリンクリストです。

この問題では、事前定義された単一リンクリストの要素を、代替の奇数および偶数の単一リンクリストを定義する2つの方法のいずれかで再配置する必要があります。

2つの方法があります-リンクリストの最初の要素が偶数の場合、次の要素は奇数であり、次の要素、つまり3番目の要素は再び偶数である必要があります。もう1つのタイプは、最初の要素が奇数の場合、次の要素は偶数で、次の要素、つまり3番目の要素は奇数である必要があります。

概念をよりよく理解するために例を見てみましょう。

リンクリストが− 45> 21> 2> 213> 3> 34>78>12であるとします。

結果のリンクリストは、45> 2> 21> 34> 213> 78> 3> 12

さて、このリンクリストには偶数と奇数の要素があるので、これらを再配置するために、2、34、78、12を連続する偶数の位置に配置し、45、21、213、3を連続する奇数の位置に配置します。

ここで、問題を理解したので、これに対する解決策を見つけようとします。このタイプの問題を解決するには、複数の方法があります。簡単な方法は、スタックを使用することです。 2つのスタックを作成します。1つは偶数用、もう1つは奇数値用です。順不同のノード、つまり奇数の位置にある偶数のノードに遭遇した場合、アドレスを偶数のスタックにプッシュし、同様に奇数のスタックにもプッシュします。そして最後に、トラバースした後、ノードをスタックからポップします。

このロジックに基づいて、アルゴリズムを作成します-

アルゴリズム

Step 1 : Create stacks for holding out of order even and odd node of the linked list.
Step 2 : Traverse the linked list and follow :
   Step 2.1 : if odd node is out of order i.e. at odd position, push it to odd stack.
   Step 2.2 : If even node is out of order i.e. at even position, push it to even stack.
Step 3 : Push elements from the stack in alternate order. When the stack is empty, the result is the required linked list.
Step 4: Print the elements of the linked list.

例

#include <bits/stdc++.h>
using namespace std;
struct Node {
   int data;
   struct Node* next;
};
void printList(struct Node* node) ;
Node* newNode(int key){
   Node* temp = new Node;
   temp->data = key;
   temp->next = NULL;
   return temp;
}
Node* insertBeg(Node* head, int val){
   Node* temp = newNode(val);
   temp->next = head;
   head = temp;
   return head;
}
void OddEvenList(Node* head) ;
int main(){
   Node* head = newNode(45);
   head = insertBeg(head, 21);
   head = insertBeg(head, 2);
   head = insertBeg(head, 213);
   head = insertBeg(head, 3);
   head = insertBeg(head, 34);
   head = insertBeg(head, 78);
   head = insertBeg(head, 12);
   cout << "Linked List:" << endl;
   printList(head);
   OddEvenList(head);
   cout << "Linked List after "
   << "Rearranging:" << endl;
   printList(head);
   return 0;
}
void printList(struct Node* node){
   while (node != NULL) {
      cout << node->data << " ";
      node = node->next;
   }
   cout << endl;
}
void OddEvenList(Node* head){
   stack<Node*> odd;
   stack<Node*> even;
   int i = 1;
   while (head != nullptr) {
      if (head->data % 2 != 0 && i % 2 == 0) {
         odd.push(head);
      }
      else if (head->data % 2 == 0 && i % 2 != 0) {
         even.push(head);
      }
      head = head->next;
      i++;
   }
   while (!odd.empty() && !even.empty()) {
      swap(odd.top()->data, even.top()->data);
      odd.pop();
      even.pop();
   }
}

出力

Linked List:
12 78 34 3 213 2 21 45
Linked List after Rearranging:
3 78 45 12 213 2 21 34