题目描述
输入n个整数，逐个读入建立一个单链表，然后将该单链表拆分成两个子链表，第一个子链表存放所有的偶数，第二个子链表存放所有的奇数，两个子链表中数据的相对次序与原链表一致。
测试
测试用例1
输入:
输入分为两行：
第1行输入整数的个数n；
第2行依次输入n个整数，每个整数之间以空格分割。
如：
11
10 3 25 8 15 39 9 70 6 100 67
输出：
输出分为3行：
第1行为偶数和奇数数据元素的个数；
第2行依次输出偶数子链表的所有数据，没有偶数，输出一个换行；
第3行依次输出奇数子链表的所有数据，没有奇数，输出一个换行。
如：
5 6
10 8 70 6 100
3 25 15 39 9 67
程序实现（C++）：
#include <bits/stdc++.h>
using namespace std;
// 定义单链表结点
struct Node {
int data;
Node* next;
Node(int val) : data(val), next(nullptr) {}
};
// 创建单链表，链表带有头结点，n 为输入元素个数，返回链表头指针
Node* create(int n) {
Node* head = new Node(0);
for (int i = 0; i < n; ++i) {
int val;
cin >> val;
Node* newNode = new Node(val);
newNode->next = head->next;
head->next = newNode;
}
return head;
}
// 拆分链表，将单链表拆分成两个链表，第一个链表（head1）使用原链表表头，存放所有的偶数元素，第二个子链表（head2，带头结点）存放所有的奇数元素，两个子链表中数据的相对次序与原链表一致。
Node* split(Node* head1) {
int evenCount = 0;
int oddCount = 0;
Node* head2 = new Node(0);
Node* p = head1->next;
head1->next = nullptr;
Node* q;
while (p) {
q = p->next;
if (p->data % 2 == 0) {
// 偶数元素，插入 head1 链表头部，元素再次逆序
p->next = head1->next;
head1->next = p;
evenCount++;
} else {
// 奇数元素，插入 head2 链表头部，元素再次逆序
p->next = head2->next;
head2->next = p;
oddCount++;
}
p = q;
}
cout << evenCount << " " << oddCount << endl;
return head2;
}
// 顺序输出带头结点的单链表中各数据元素
void show(Node* head) {
Node* p = head->next;
while (p) {
cout << p->data;
if (p->next) {
cout << " ";
}
p = p->next;
}
cout << endl;
}
int main() {
int n;
cin >> n;
Node* head1 = create(n);
Node* head2 = split(head1);
show(head1);
show(head2);
return 0;
}