資料結構
網路
關係資料庫管理系統
作業系統
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 次瀏覽
廣告