จากรายชื่อที่เชื่อมโยงในบทช่วยสอนนี้ และเราจำเป็นต้องเก็บตัวเลขทั้งหมดที่น้อยกว่า x ที่จุดเริ่มต้นของรายการและตัวเลขอื่นๆ ที่ด้านหลัง เรายังต้องรักษาคำสั่งของพวกเขาเหมือนเดิม เช่น
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
เพื่อแก้ปัญหานี้ เราจำเป็นต้องสร้างรายการเชื่อมโยงสามรายการในตอนนี้ เมื่อเราพบตัวเลขที่น้อยกว่า x เราจะใส่มันเข้าไปในรายการแรก ตอนนี้สำหรับค่าที่เท่ากับ x เราใส่มันในวินาที และสำหรับค่าที่มากกว่า เราใส่มันในสามตอนนี้ ในท้ายที่สุด เราเชื่อมรายการและพิมพ์รายการสุดท้าย
แนวทางในการหาแนวทางแก้ไข
ในแนวทางนี้ เราจะรักษารายการสามรายการ ได้แก่ เล็ก เท่ากัน ใหญ่ ตอนนี้เรารักษาลำดับและรวมรายการเป็นรายการสุดท้าย ซึ่งเป็นคำตอบของเรา
ตัวอย่าง
รหัส C++ สำหรับแนวทางข้างต้น
#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;
} ผลลัพธ์
2 10 4 5 30
คำอธิบายของโค้ดด้านบน
ในแนวทางที่อธิบายข้างต้น เราจะเก็บรายการเชื่อมโยงสามรายการที่มีเนื้อหาตามลำดับ รายการที่เชื่อมโยงทั้งสามนี้จะมีองค์ประกอบที่เล็กกว่า เท่ากัน และมากกว่า x แยกจากกัน งานของเราง่ายขึ้นในขณะนี้ เราจำเป็นต้องเชื่อมรายการแล้วคืนหัว
บทสรุป
ในบทช่วยสอนนี้ เราจะแก้ปัญหาการแบ่งพาร์ติชั่นรายการที่มีการเชื่อมโยงรอบค่าที่กำหนดและคงลำดับเดิมไว้ นอกจากนี้เรายังได้เรียนรู้โปรแกรม C++ สำหรับปัญหานี้และแนวทางที่สมบูรณ์ (ปกติ) ซึ่งเราแก้ไขปัญหานี้ เราสามารถเขียนโปรแกรมเดียวกันในภาษาอื่นๆ เช่น C, java, python และภาษาอื่นๆ เราหวังว่าคุณจะพบว่าบทช่วยสอนนี้มีประโยชน์
