1052: [编程入门]链表合并

解题思路:

主要需要解决的问题：（1）如何合并（2）如何排序

是一边排序一边合并呢？还是先合并再排序呢？我选择了后者。

一共写了5个子函数，分别用于创建链表，打印链表，合并链表，交换两结点数据，排序（需要调用前一个）。其中创建用的是尾插法，排序用的是选择排序。

链表的操作其实没有什么算法的逻辑在其中，主要是结构中带了个指针，理解起来比较抽象，理清操作的先后顺序就好了。

注意事项:

（1）链表的头结点是不存数据的。尾结点是指向NULL的。

（2）看了置顶答案，有人在写结构时的写法是：

typedef struct student{ }*node, Node;

分别定义了指针对象和普通对象，可能比我的好理解一点，我的在传参时全是用的指针，容易和其中的next指针搞混。

参考代码:

#include <iostream>
using namespace std;

struct Student {
	int id; // 学号
	int score; // 成绩
	Student* next; // next指针
};

Student* createStudent(int n); // 创建链表
void printStudent(Student* head); // 打印链表
void swapStudent(Student* s1, Student* s2); // 交换链表中两个结点的数据（指针不变）
void appendStudent(Student* s1, Student* s2); // 合并s2到s1
void sortStudent(Student* s); // 链表排序
int main() {
	int N = 0; // 链表1学生数
	int M = 0; // 链表2学生数
	cin >> N >> M;
	Student* s1 = createStudent(N); // 链表1
	Student* s2 = createStudent(M); // 链表2
	appendStudent(s1, s2); // 合并
	sortStudent(s1); // 排序
	printStudent(s1); // 打印
	return 0;
}

Student* createStudent(int n) {
	Student* head = (Student*)malloc(sizeof(Student)); // 创建头结点并分配空间
	head->next = NULL; // 定义头结点next指针
	Student* p = head; // 定位指针，表示新结点的“上一个结点”
	Student* newInfo; // 新结点，用于存储输入的数据
	for (int i = 0; i < n; i++) {
		newInfo = (Student*)malloc(sizeof(Student)); // 分配空间
		cin >> newInfo->id >> newInfo->score; // 读输入
		// 尾插法
		newInfo->next = p->next; // 新结点的next指向上一个结点的next（尾插法中即为NULL）
		p->next = newInfo; // 上一个结点的next指向新结点
		p = newInfo; // 新结点变成下一个新结点的“上一个结点”
	}
	return head; // 返回创建完毕的链表的头结点
}

void printStudent(Student* head) {
	Student* p = head->next; // 定位指针，用于打印，从头结点的下一个结点开始（头结点没数据）
	Student* del; // 定位指针，用于释放空间
	while (p != NULL) {
		cout << p->id << " " << p->score << endl; // 打印
		// 释放打印完的结点
		del = p; // 定位至准备释放的结点
		p = p->next; // 定位至下一个待打印的结点
		free(del); // 释放
	}
}

void swapStudent(Student* s1, Student* s2) {
	// 和正常的交换数据操作一致，需要建两个temp变量
	int tempId = s1->id;
	int tempScore = s1->score;
	s1->id = s2->id;
	s1->score = s2->score;
	s2->id = tempId;
	s2->score = tempScore;
}

void appendStudent(Student* s1, Student* s2) {
	Student* tail = s1; // 定位指针，用于找到s1的尾结点
	s2 = s2->next; // s2的头结点没数据
	while (tail->next != NULL) {
		tail = tail->next; // 找到尾结点
	}
	tail->next = s2; // LINK START!
}

void sortStudent(Student* s) {
	Student* start = s->next; // 定位指针，表示每轮循环的开始（即选择排序中待排区的第一个结点）
	while (start != NULL) {
		Student* p = start; // 定位指针，用于找到此轮循环的最小值结点
		int minId = p->id; // 用于存储最小值
		Student* min = p; // 定位指针，表示最小值的结点
		while (p != NULL) {
			if (p->id < minId) {
				minId = p->id; // 更新最小值
				min = p; // 更新最小值结点
			}
			p = p->next;
		}
		swapStudent(min, start); // 把最小值结点和待排区第一个结点交换数据
		start = start->next; // 下一轮循环的开始结点
	}
}