链表合并，总结链表的用法和注意事项

题目描述：

已有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

代码实现：

#include <stdio.h>
#include <stdlib.h>

typedef struct student
{
	int num;
	int score;
	struct student* next;
} stud;

 
//创建链表，参数n为需要输入的数据个数
/*
	总结方法步骤以及注意事项,创建建立链表函数,参数为需要输入数据的个数
先创立没有数据的头节点(运用动态内存申请malloc),每一次的动态内存申请所
用的指针都要用if操作,如果为空就跳出循环.然后定义一个变量tmp并接收head
的地址以操作head内的空间(为什么要用tmp,个人理解为更加清晰可观,便于理解
因为后面有tmp = newNode操作)再就循环输入数据.这里面又要重新定义一个
新变量newNode来存入输入的数据,然后再运用链表的连接,将它接入链表的末尾.
最后一步tmp = newNode,则移动了tmp所指的位置,从头移向下一个节点(从
这一个节点移到下一个节点) 
*/
stud* creatNode(int n)
{
	stud* head = (stud*)malloc(sizeof(stud));
	if(head == NULL) return NULL;
	//创建头节点并初始化 
	head->num = 0;
	head->score = 0;
	head->next = NULL;
	
//指针=指针意味着将head的地址传给tmp，或者说覆盖给tmp,则tmp能操作
//之前head指向的内存空间,所以最后写返回head和返回tmp都可以 
	stud* tmp = head;
	int i;
	for(i = 0; i < n; i++)
	{
		stud* newNode = (stud*)malloc(sizeof(stud));
		if(newNode == NULL) return NULL;
		scanf("%d%d", &newNode->num, &newNode->score);
		newNode->next = NULL;
		tmp->next = newNode;
		tmp = newNode;
//移动了tmp所指的位置,从头移向下一个节点(从这一个节点移到下一个节点
	}
	return head; 
}

//连接两个链表,将逗号后面的链表连接到前面的链表 
stud* linkNode(stud* student1, stud* student2)
{
	if(student1 == NULL || student2 == NULL) return NULL;
	stud* tmp1 = student1;
	stud* tmp2 = student2;
	//先循环第一个链表,让tmp指向链表的末尾 
	while(tmp1->next != NULL)
	{
		tmp1 = tmp1->next;
	}
	//连接两个链表
	tmp1->next = tmp2->next;//tmp2的next就是头指针的尾,即除表头之外的所有数据 
	free(tmp2);
	return student1;
}

//对新链表进行排序 
void sortLinklist(stud* student)
{
	if(student == NULL) return;
	
	//选择法排序 
	stud* tmp1 = NULL;
	stud* tmp2 = NULL;
//注意结束条件,外层循环是tmp1->next!=NULL,内层循环是tmp2!=NULL 
	for(tmp1 = student->next; tmp1->next != NULL; tmp1 = tmp1->next)
	{
		for(tmp2 = tmp1->next; tmp2 != NULL; tmp2 = tmp2->next)
		{
			if(tmp1->num > tmp2->num)
			{
				stud temp;
				//数据域的交换 
				temp = *tmp1;
				*tmp1 = *tmp2;
				*tmp2 = temp;
				//指针域的交换
				temp.next = tmp1->next;
				tmp1->next = tmp2->next;
				tmp2->next = temp.next; 
			}
		}
	}
}

//链表的打印
void printLinklist(stud* student)
{
	if(student == NULL || student->next == NULL)
	{
		printf("invald list");
		return;
	}
	
	stud* p = student;
	//注意是p!=NULL而不是p->next!=NULL,不然会少打一个数据 
	for(p = student->next; p != NULL; p = p->next)
	{
		printf("%d %d\n", p->num, p->score);
	}
}

//释放链表
void destroyList(stud* student)
{
	if(student == NULL) return;
	
	stud* p = student;
	stud* tmp = NULL;
	
	while(p != NULL)
	{
		tmp = p->next;
		free(p);
		p = tmp;
	}
}

int main()
{
	int n, m;
	scanf("%d%d", &n, &m);
	//创建两个链表 
	stud* student1 = creatNode(n);
	stud* student2 = creatNode(m);
	//连接两个链表 
	stud* student = linkNode(student1, student2);
	//排序新链表
	sortLinklist(student);
	//打印排序后的链表 
	printLinklist(student);
	//释放链表
	destroyList(student);
	return 0;
}