C ++单链接列表中的交替奇偶节点

单个链接列表是一个线性数据结构，包含两个部分-一个数据和指向列表中下一个元素的其他指针。

另一种奇数和偶数链表是一个链表，该链表的一个节点具有偶数数据，另一个节点具有奇数数据成员。

在此问题中，我们必须以两种定义备用奇数和偶数单链接列表的方式中的任何一种来重新排列预定义单链接列表的元素。

两种方式是-“链接”列表的第一个元素为偶数，然后下一个元素应为奇数，而下一个元素即第二个元素，则为偶数。另一种类型是，如果第一个元素为奇数，则下一个元素应为偶数，而下一个元素即第三元素为奇数。

让我们看一个例子，以更好地理解该概念。

假设链接列表为-45> 21> 2> 213> 3> 34> 78> 12。

生成的链接列表将为45> 2> 21> 34> 213> 78> 3> 12

现在，由于在此链表中我们具有偶数和奇数元素，并且要重新排列它们，我们将2、34、78、12置于连续的偶数位置，并将45、21、213、3置于连续的奇数位置。

现在，我们已经了解了问题，我们将尝试为此找到解决方案。解决这类问题可以有多种方式。一种简单的方法是使用堆栈。我们将创建两个堆栈，一个用于偶数，一个用于奇数。如果遇到任何乱序节点，即偶数节点位于奇数位置，我们会将地址推入偶数堆栈，同样将地址推入奇数堆栈。遍历结束时，我们将节点弹出堆栈。

基于此逻辑，我们将创建一个算法-

算法

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 << "链接列表：" << 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();
   }
}

输出结果

链接列表：
12 78 34 3 213 2 21 45
Linked List after Rearranging:
3 78 45 12 213 2 21 34