Danh sách được liên kết đơn là cấu trúc dữ liệu tuyến tính chứa hai phần - một dữ liệu và các con trỏ khác đến phần tử tiếp theo trong danh sách.
Danh sách liên kết lẻ và chẵn thay thế là danh sách được liên kết có một nút có dữ liệu chẵn và nút còn lại có các thành viên dữ liệu lẻ.
Trong vấn đề này, chúng ta phải sắp xếp lại các phần tử của danh sách liên kết đơn lẻ được xác định trước theo một trong hai cách xác định danh sách liên kết đơn lẻ và chẵn thay thế.
Có hai cách là - phần tử đầu tiên của danh sách được Liên kết là chẵn thì phần tử tiếp theo phải là số lẻ và phần tử tiếp theo bên cạnh, tức là phần tử thứ ba lại chẵn. Loại khác sẽ là nếu phần tử đầu tiên là lẻ thì phần tử tiếp theo phải là chẵn và phần tử tiếp theo, tức là phần tử thứ ba là lẻ.
Hãy xem một ví dụ để hiểu rõ hơn về khái niệm này.
Giả sử danh sách được liên kết là - 45> 21> 2> 213> 3> 34> 78> 12.
Danh sách liên kết kết quả sẽ là 45> 2> 21> 34> 213> 78> 3> 12
Bây giờ, vì trong danh sách liên kết này chúng ta có phần tử chẵn và lẻ và để sắp xếp lại chúng, chúng ta sẽ đặt 2, 34, 78, 12 ở các vị trí chẵn liên tiếp và 45, 21, 213, 3 ở các vị trí lẻ liên tiếp.
Bây giờ, khi chúng tôi đã hiểu vấn đề, chúng tôi sẽ cố gắng tìm ra giải pháp cho vấn đề này. Có thể có nhiều cách để giải quyết loại vấn đề này. Một phương pháp đơn giản sẽ là sử dụng ngăn xếp. Chúng tôi sẽ tạo hai ngăn xếp, một ngăn xếp cho giá trị chẵn và một ngăn xếp cho giá trị lẻ. Nếu chúng ta gặp bất kỳ nút không theo thứ tự nào, tức là nút chẵn ở vị trí lẻ, chúng ta sẽ đẩy địa chỉ sang ngăn xếp chẵn và tương tự đối với ngăn xếp lẻ. Và cuối cùng sau khi duyệt qua, chúng tôi sẽ bật các nút ra khỏi ngăn xếp.
Dựa trên logic này, chúng tôi sẽ tạo ra một thuật toán -
Thuật toán
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.
Ví dụ
#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();
}
} Đầu ra
Linked List: 12 78 34 3 213 2 21 45 Linked List after Rearranging: 3 78 45 12 213 2 21 34