Đưa ra một danh sách được liên kết trong hướng dẫn này và chúng ta cần giữ tất cả các số nhỏ hơn x ở đầu danh sách và các số khác ở phía sau. Chúng tôi cũng cần giữ lại thứ tự của họ như trước đây. ví dụ
Input : 1->4->3->2->5->2->3, x = 3 Output: 1->2->2->3->3->4->5 Input : 1->4->2->10 x = 3 Output: 1->2->4->10 Input : 10->4->20->10->3 x = 3 Output: 3->10->4->20->10
Để giải quyết vấn đề này, chúng ta cần tạo ba danh sách liên kết ngay bây giờ. Khi chúng ta gặp một số nhỏ hơn x, thì chúng ta sẽ chèn nó vào danh sách đầu tiên. Bây giờ đối với giá trị bằng x, chúng tôi đặt nó ở vị trí thứ hai, và đối với giá trị lớn hơn, chúng tôi chèn nó vào thứ ba ngay bây giờ. Cuối cùng, chúng tôi nối các danh sách và in ra danh sách cuối cùng.
Phương pháp tiếp cận để tìm giải pháp
Trong cách tiếp cận này, chúng tôi sẽ duy trì ba danh sách, cụ thể là nhỏ, bằng nhau, lớn. Bây giờ chúng tôi duy trì thứ tự của chúng và nối các danh sách thành một danh sách cuối cùng, đó là câu trả lời của chúng tôi.
Ví dụ
Mã C ++ cho phương pháp tiếp cận trên
#include<bits/stdc++.h>
using namespace std;
struct Node{ // structure for our node
int data;
struct Node* next;
};
// A utility function to create a new node
Node *newNode(int data){
struct Node* new_node = new Node;
new_node->data = data;
new_node->next = NULL;
return new_node;
}
struct Node *partition(struct Node *head, int x){
struct Node *smallhead = NULL, *smalllast = NULL; // we take two pointers for the list //so that it will help us in concatenation
struct Node *largelast = NULL, *largehead = NULL;
struct Node *equalhead = NULL, *equallast = NULL;
while (head != NULL){ // traversing through the original list
if (head->data == x){ // for equal to x
if (equalhead == NULL)
equalhead = equallast = head;
else{
equallast->next = head;
equallast = equallast->next;
}
}
else if (head->data < x){ // for smaller than x
if (smallhead == NULL)
smalllast = smallhead = head;
else{
smalllast->next = head;
smalllast = head;
}
}
else{ // for larger than x
if (largehead == NULL)
largelast = largehead = head;
else{
largelast->next = head;
largelast = head;
}
}
head = head->next;
}
if (largelast != NULL) // largelast will point to null as it is our last list
largelast->next = NULL;
/**********Concatenating the lists**********/
if (smallhead == NULL){
if (equalhead == NULL)
return largehead;
equallast->next = largehead;
return equalhead;
}
if (equalhead == NULL){
smalllast->next = largehead;
return smallhead;
}
smalllast->next = equalhead;
equallast->next = largehead;
return smallhead;
}
void printList(struct Node *head){ // function for printing our list
struct Node *temp = head;
while (temp != NULL){
printf("%d ", temp->data);
temp = temp->next;
}
}
int main(){
struct Node* head = newNode(10);
head->next = newNode(4);
head->next->next = newNode(5);
head->next->next->next = newNode(30);
head->next->next->next->next = newNode(2);
head->next->next->next->next->next = newNode(50);
int x = 3;
head = partition(head, x);
printList(head);
return 0;
} Đầu ra
2 10 4 5 30
Giải thích về Quy tắc trên
Trong cách tiếp cận được mô tả ở trên, chúng tôi sẽ giữ ba danh sách được liên kết với nội dung theo trình tự tuần tự. Ba danh sách được liên kết này sẽ chứa các phần tử nhỏ hơn, bằng và lớn hơn x một cách riêng biệt. Nhiệm vụ của chúng tôi bây giờ được đơn giản hóa. Chúng ta cần nối các danh sách và sau đó trả về phần đầu.
Kết luận
Trong hướng dẫn này, chúng tôi giải quyết Phân vùng danh sách liên kết xung quanh một giá trị nhất định và giữ thứ tự ban đầu. Chúng tôi cũng đã học chương trình C ++ cho vấn đề này và cách tiếp cận hoàn chỉnh (Bình thường) mà chúng tôi đã giải quyết vấn đề này. Chúng ta có thể viết cùng một chương trình bằng các ngôn ngữ khác như C, java, python và các ngôn ngữ khác. Chúng tôi hy vọng bạn thấy hướng dẫn này hữu ích.