รายการที่เชื่อมโยงเดียวคือโครงสร้างข้อมูลเชิงเส้นที่มีสองส่วน - ข้อมูลหนึ่งและตัวชี้อื่น ๆ ไปยังองค์ประกอบถัดไปในรายการ
รายการอื่นที่เชื่อมโยงแบบคู่และคี่ เป็นรายการที่เชื่อมโยงซึ่งมีหนึ่งโหนดที่มีข้อมูลคู่และอีกโหนดหนึ่งที่มีสมาชิกข้อมูลคี่
ในปัญหานี้ เราต้องจัดเรียงองค์ประกอบของรายการที่เชื่อมโยงที่กำหนดไว้ล่วงหน้าโดยวิธีใดวิธีหนึ่งจากสองวิธี ซึ่งจะกำหนดรายการที่เชื่อมโยงแบบคี่และแบบคู่แม้เพียงตัวเดียว
สองวิธีคือ – องค์ประกอบแรกของรายการที่เชื่อมโยงเป็นเลขคู่ จากนั้นองค์ประกอบถัดไปควรเป็นเลขคี่ และองค์ประกอบถัดไปถัดไปคือองค์ประกอบที่สามเป็นเลขคู่อีกครั้ง อีกประเภทหนึ่งอาจเป็นถ้าองค์ประกอบแรกเป็นเลขคี่ จากนั้นองค์ประกอบถัดไปควรเป็นเลขคู่และถัดจากองค์ประกอบถัดไปคือองค์ประกอบที่สามเป็นเลขคี่
มาดูตัวอย่างเพื่อทำความเข้าใจแนวคิดกันดีกว่า
สมมติว่ารายการที่เชื่อมโยงคือ − 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
