数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究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 << "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
更新于: 2019年10月16日
286 次浏览
广告