《算法笔记》7.3小节——数据结构专题(1)-＞链表处理-＞问题 B: C语言-链表排序

题目描述：

已有a、b两个链表，每个链表中的结点包括学号、成绩。要求把两个链表合并，按学号升序排列。

输入

第一行，a、b两个链表元素的数量N、M,用空格隔开。 接下来N行是a的数据 然后M行是b的数据 每行数据由学号和成绩两部分组成

输出

按照学号升序排列的数据

样例输入

2 3
5 100
6 89
3 82
4 95
2 10

样例输出

2 10
3 82
4 95
5 100
6 89

代码C++

// 不需创建a、b链表后再排序，在建立链表的过程中排序即可
#include<cstdio>
struct stu {int id;int score;stu* next;// 构造新节点stu(int x, int y): id(x), score(y), next(nullptr){}
};
int main() {int n, m;scanf("%d%d", &n, &m);// 建立一个头节点stu* head = new stu(-1, -1);for (int i = 0; i < n + m; i++) {int x, y;scanf("%d%d", &x, &y);// 创建新节点接收新数据stu* temp = new stu(x, y);// 快慢节点，每次循环快节点指向头节点，慢节点指向头节点的下一节点stu* slow = head;stu* fast = head->next;if (fast != nullptr) {// 判定条件，头节点的下一节点存在，而且快节点id小于插入节点id,快慢节点后移，直至找到快节点大于要插入数据，慢节点小于要插入数据while (fast && fast->id < temp->id) {fast = fast->next;slow = slow->next;}// 将要插入节点插入到慢节点之后，快节点之前temp->next = fast;slow->next = temp;}// 第一次插入的特殊情况，慢节点指向头节点，快节点为空else {slow->next = temp;}}// 遍历循环输出stu* ptr = head->next;while (ptr) {printf("%d %d\\n", ptr->id, ptr->score);ptr = ptr->next;}return 0;
}