Giả sử chúng ta có một danh sách liên kết và một giá trị x. Chúng ta phải làm các vách ngăn. Phân vùng sao cho tất cả các nút nhỏ hơn x đến trước các nút lớn hơn hoặc bằng x. Chúng ta nên bảo toàn thứ tự tương đối ban đầu của các nút trong mỗi phân vùng trong số hai phân vùng này. Vì vậy, nếu danh sách giống như [1,4,3,2,5,2] và x =3, thì đầu ra sẽ là [1,2,2,4,3,5]
Để giải quyết vấn đề này, chúng ta sẽ làm theo các bước sau -
- Tạo các nút giả d1 và d2 và khởi tạo chúng bằng -1, tạo hai con trỏ dp1 và dp2, chúng trỏ đến d1 và d2 tương ứng.
- trong khi a không null
- if giá trị của a
- tiếp theo của dp1:=một nút mới có giá trị là một
- dp1:=con trỏ tiếp theo của dp1
- if giá trị của a
- nếu không thì
- tiếp theo của dp2:=một nút mới có giá trị là một
- dp2:=con trỏ tiếp theo của dp2
- a:=tiếp theo của một
Ví dụ (C ++)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#include <bits/stdc++.h>
using namespace std;
class ListNode{
public:
int val;
ListNode *next;
ListNode(int data){
val = data;
next = NULL;
}
};
ListNode *make_list(vector<int> v){
ListNode *head = new ListNode(v[0]);
for(int i = 1; i<v.size(); i++){
ListNode *ptr = head;
while(ptr->next != NULL){
ptr = ptr->next;
}
ptr->next = new ListNode(v[i]);
}
return head;
}
void print_list(ListNode *head){
ListNode *ptr = head;
cout << "[";
while(ptr->next){
cout << ptr->val << ", ";
ptr = ptr->next;
}
cout << "]" << endl;
}
class Solution {
public:
ListNode* partition(ListNode* a, int b) {
ListNode* dummy1 = new ListNode(-1);
ListNode* dummy2 = new ListNode(-1);
ListNode* dummyPtr1 = dummy1;
ListNode* dummyPtr2 = dummy2;
while(a){
if(a->val < b){
dummyPtr1->next = new ListNode(a->val);
dummyPtr1 = dummyPtr1->next;
}
else{
dummyPtr2->next = new ListNode(a->val);
dummyPtr2 = dummyPtr2->next;
}
a = a->next;
}
dummyPtr1->next = dummy2->next;
return dummy1->next;
}
};
main(){
Solution ob;
vector<int> v = {1,4,6,3,2,5,2,8};
ListNode *head = make_list(v);
print_list(ob.partition(head, 3));
} Đầu vào
[1,4,6,3,2,5,2,8] 3
Đầu ra
[1, 2, 2, 4, 6, 3, 5, ]