如何做好单链表的分割

单链表的分割

将一个单链表以某个元素基准分割为两个链表

提示:

1输入若干数值创建一一个单链表(-1表示结束)2输出该初始单链表

3输入一一个基准值X

4分割为两个单链表(一个单链表的元素值均小于基准，另一个单链表的元素值均大于等于基准)5输出分割后的两个链表

“Devil组”引证GPT后的撰写：

#include <iostream>
using namespace std;

// 定义单链表结构体
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

ListNode* partitionList(ListNode* head, int x) {
    ListNode* lessHead = new ListNode(0);
    ListNode* lessTail = lessHead;
    ListNode* greaterHead = new ListNode(0);
    ListNode* greaterTail = greaterHead;
    ListNode* cur = head;

    while (cur) {
        if (cur->val < x) {
            lessTail->next = cur;
            lessTail = cur;
        } else {
            greaterTail->next = cur;
            greaterTail = cur;
        }
        cur = cur->next;
    }

    greaterTail->next = NULL;
    lessTail->next = greaterHead->next;
    return lessHead->next;
}

int main() {
    // 输入若干数值创建单链表
    int val;
    ListNode* head = new ListNode(0);
    ListNode* cur = head;
    cin >> val;
    while (val != -1) {
        ListNode* node = new ListNode(val);
        cur->next = node;
        cur = cur->next;
        cin >> val;
    }
    head = head->next;

    // 输出初始单链表
    cout << "Initial List: ";
    cur = head;
    while (cur) {
        cout << cur->val << " ";
        cur = cur->next;
    }
    cout << endl;

    // 输入基准值X
    int x;
    cin >> x;

    // 分割单链表
    ListNode* newHead = partitionList(head, x);

    // 输出分割后的两个链表
    cout << "Less than " << x << ": ";
    cur = newHead;
    while (cur && cur->val < x) {
        cout << cur->val << " ";
        cur = cur->next;
    }
    cout << endl;
    cout << "Greater than or equal to " << x << ": ";
    while (cur) {
        cout << cur->val << " ";
        cur = cur->next;
    }
    cout << endl;

    return 0;
}