C++ Phân vùng danh sách liên kết quanh giá trị x giữ thứ tự

Cho danh sách liên kết, sắp xếp lại sao cho các nút < x ở đầu, = x ở giữa, > x ở cuối, giữ nguyên thứ tự tương đối trong mỗi nhóm. 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

Phương pháp giải

Tạo 3 danh sách: small (x). Duyệt danh sách gốc, phân phát nút vào 3 danh sách. Cuối cùng nối 3 danh sách theo thứ tự small→equal→large.

Ví dụ minh họa

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    Node* next;
};

Node* newNode(int data) {
    Node* n = new Node();
    n->data = data; n->next = NULL;
    return n;
}

Node* partition(Node* head, int x) {
    Node *sh=NULL, *st=NULL, *eh=NULL, *et=NULL, *lh=NULL, *lt=NULL;

    while (head) {
        if (head->data == x) {
            if (!eh) eh = et = head;
            else { et->next = head; et = head; }
        } else if (head->data < x) {
            if (!sh) sh = st = head;
            else { st->next = head; st = head; }
        } else {
            if (!lh) lh = lt = head;
            else { lt->next = head; lt = head; }
        }
        head = head->next;
    }

    if (lt) lt->next = NULL;
    if (!sh) {
        if (!eh) return lh;
        et->next = lh; return eh;
    }
    if (!eh) { st->next = lh; return sh; }
    st->next = eh; et->next = lh; return sh;
}

void printList(Node* head) {
    while (head) { cout << head->data << " "; head = head->next; }
}

int main() {
    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;
}

Kết quả

2 10 4 5 30

Giải thích

Giữ 3 con trỏ head/tail cho mỗi nhóm. Phân phát nút theo giá trị so với x. Nối 3 nhóm theo thứ tự.

Kết luận

Đã giải bài toán phân vùng danh sách liên kết quanh x giữ thứ tự bằng 3 danh sách phụ. Code C++ chuyển được sang Java, Python, C. Hy vọng hữu ích.