编写一个程序exp2-7.cpp,以单链表的首结点值x为基准讲该单链表分割为两部分，使所有小于x的结点排在大于或等于x的结点之前

#include <iostream>

using namespace std;

struct Node {
    int val;
    Node* next;
    Node(int v): val(v), next(nullptr) {}
};

void insert(Node*& head, int val) {
    Node* newNode = new Node(val);
    if (head == nullptr) {
        head = newNode;
    } else {
        Node* cur = head;
        while (cur->next != nullptr) {
            cur = cur->next;
        }
        cur->next = newNode;
    }
}

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

void partition(Node*& head, int x) {
    Node* smallHead = nullptr, *smallTail = nullptr;
    Node* bigHead = nullptr, *bigTail = nullptr;
    Node* cur = head;
    while (cur != nullptr) {
        if (cur->val < x) {
            if (smallHead == nullptr) {
                smallHead = smallTail = cur;
            } else {
                smallTail->next = cur;
                smallTail = cur;
            }
        } else {
            if (bigHead == nullptr) {
                bigHead = bigTail = cur;
            } else {
                bigTail->next = cur;
                bigTail = cur;
            }
        }
        cur = cur->next;
    }
    if (smallTail != nullptr) {
        smallTail->next = bigHead;
        head = smallHead;
    } else {
        head = bigHead;
    }
    if (bigTail != nullptr) {
        bigTail->next = nullptr;
    }
}

int main() {
    Node* head = nullptr;
    insert(head, 3);
    insert(head, 1);
    insert(head, 5);
    insert(head, 2);
    insert(head, 4);
    cout << "Original list: ";
    printList(head);
    partition(head, 3);
    cout << "After partition: ";
    printList(head);
    return 0;
}