c++设计程序将一个数值类型数据元素的单链表按数据的奇偶性分解成两个单链表

在 C++ 中，要设计一个程序将一个数值类型的单链表按奇偶性分解成两个单独的链表，你可以创建两个新的链表，一个存储奇数，另一个存储偶数。这里是一个基本的步骤概述：

1. **定义结构**:
首先，定义一个链表节点（Node），包含数据元素和指向下一个节点的指针。

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

2. **定义辅助函数**:
- 创建新的奇数链表和偶数链表头结点 `headOdd` 和 `headEven`。
- 定义遍历原链表的递归函数 `partitionList`。

Node* partitionList(Node* head) {
    // 如果链表为空，直接返回
    if (head == nullptr) return nullptr;

    // 分治策略：处理第一个节点
    Node* oddHead = new Node{head->data % 2 ? head->data : 0, nullptr};
    Node* evenHead = new Node{(head->data % 2 == 0) ? head->data : 0, nullptr};

    // 递归处理剩余部分
    Node* tailOdd = partitionList(head->next);
    tailOdd->next = oddHead; // 将当前奇数链接到新链表的末尾

    head->next = evenHead; // 原头节点指向新偶数链表
    if (evenHead->data != 0) { // 如果有新偶数节点，更新新链表头
        oddHead->next = evenHead;
    }

    return tailOdd; // 返回奇数链表的尾部
}

3. **主函数**:
在主函数中，创建链表并调用 `partitionList` 函数。

int main() {
    // 初始化并构建原始链表...
    Node* list = createLinkedList(); // 假设有一个createLinkedList()函数生成链表

    // 分解链表
    Node* tailOdd = partitionList(list);

    // 输出或进一步处理两个链表...
    printList(oddHead); // 打印奇数链表
    printList(evenHead); // 打印偶数链表

    // 清理内存
    deleteTailRecursive(tailOdd);
    return 0;
}

// 辅助函数用于删除链表尾部
void deleteTailRecursive(Node* &tail) {
    if (tail == nullptr) return;
    Node *temp = tail;
    tail = tail->next;
    delete temp;
}