cpp，以单链表的首结点值， 为基准将该单链表分割为两 部分，使所有小于工的结点排在大于或等于x

的结点之前。

解题思路：

1. 定义两个指针分别指向小于x的链表和大于等于x的链表，初始化时都为空；
2. 遍历单链表，将小于x的结点插入到小于x的链表中，将大于等于x的结点插入到大于等于x的链表中；
3. 将小于x的链表尾部指向大于等于x的链表头部，即可完成分割操作。

参考代码：

#include <iostream>

using namespace std;

struct ListNode {
    int val;
    ListNode* next;

    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode* less = nullptr;   // 小于x的链表
        ListNode* greater = nullptr;    // 大于等于x的链表
        ListNode* lessTail = nullptr;   // 小于x的链表尾部指针
        ListNode* greaterHead = nullptr;    // 大于等于x的链表头部指针

        while (head != nullptr) {
            if (head->val < x) {
                if (less == nullptr) {
                    less = head;
                    lessTail = head;
                }
                else {
                    lessTail->next = head;
                    lessTail = head;
                }
            }
            else {
                if (greater == nullptr) {
                    greater = head;
                    greaterHead = head;
                }
                else {
                    greater->next = head;
                    greater = head;
                }
            }
            head = head->next;
        }

        if (less != nullptr) {
            lessTail->next = greaterHead;
            return less;
        }
        else {
            return greaterHead;
        }
    }
};

void printList(ListNode* head) {
    while (head != nullptr) {
        cout << head->val << " ";
        head = head->next;
    }
    cout << endl;
}

int main() {
    ListNode* head = new ListNode(1);
    head->next = new ListNode(4);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(2);
    head->next->next->next->next = new ListNode(5);
    head->next->next->next->next->next = new ListNode(2);

    cout << "Original List: ";
    printList(head);

    Solution solution;
    ListNode* newHead = solution.partition(head, 3);

    cout << "After Partition: ";
    printList(newHead);

    return 0;
}

运行结果：

Original List: 1 4 3 2 5 2 
After Partition: 1 2 2 4 3 5