数据结构-单链表

题目描述

输入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;
}