Giả sử chúng ta có một danh sách liên kết và một giá trị x. Ta phải phân chia danh sách sao cho tất cả các nút nhỏ hơn x đứng trước các nút lớn hơn hoặc bằng x. Giữ nguyên thứ tự tương đối ban đầu của các nút trong mỗi phân vùng. Ví dụ, danh sách [1,4,3,2,5,2] và x = 3, kết quả [1,2,2,4,3,5].
Để giải quyết, ta làm theo các bước:
- Tạo nút giả d1, d2 giá trị -1, hai con trỏ dp1, dp2 trỏ đến d1, d2.
- while a không null
- nếu giá trị a < b
- next của dp1 := nút mới giá trị a
- dp1 := next của dp1
- ngược lại
- next của dp2 := nút mới giá trị a
- dp2 := next của dp2
- a := next của a
- nếu giá trị a < b
- next của dp1 := next của d2
- return next của d1
Ví dụ (C++)
Hãy xem triển khai sau:
#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)); }Input
[1,4,6,3,2,5,2,8] 3
Output
[1, 2, 2, 4, 6, 3, 5, ]