链表合并问题

解题思路:

要实现两个链表的升序合并，我们首先要明确有几个函数：

生成链表并读取数据的函数：目的是用来生成一个空链表，并输入的信息存储在链表的节点中；

计算链表长度的函数：计算链表所含有数据节点的个数，不包含头结点

对链表进行升序排序的函数：对链表进行升序排序，采用冒泡排序的方式。两层循环，外层控制循环次数，内存控制比较次数，注意与数组不同，每轮循环开始都要将指针指向首元结点

首元结点；

将两个链表合并为一个新链表的函数：采用将两个链表合并为一个新链表的方式，合并的原则是升序排序，前提是两个链表都是有序的；

输出链表数据的函数：与数组不同，只需要把链表头指针传递给函数即可，从首元结点开始输出数据

注意事项:

代码中的链表均是包含头节点的单链表；

写代码最重要的是思路，其次是实现功能的基础编程能力；

在代码实现的过程中可能会出现很多错误，不要灰心，要注意调试

代码较长，有需要的伙伴可以优化后使用

参考代码:

/*他妈的链表*/
#include <iostream>
#include <cstdlib> 
using namespace std;
//创建链表
struct stu{
	int sn;
	int score;
}; 
typedef struct node{
	stu tempstu;
	struct node* nest;
}listnode,*listlink; 
//声明函数
void display(listlink pp); 
void creat(listlink pp,int n){
	//头插法和尾插法,采用尾插法
	//创建一个节点
	//尾插法需要一个尾结点
	listnode* tail= pp;   //初始化时：：：：尾结点等于头节点 
	for(int i=1;i<=n;++i)
	{
		//创建一个临时变量 
		listnode* ptemp= new listnode;  //C++语法
		//初始化临时变量 
		ptemp->nest=NULL;
		cin>>ptemp->tempstu.sn>>ptemp->tempstu.score; 
		//tail是机动骑兵 
		tail->nest=ptemp;
		tail=ptemp;
	}
	//算是插入数据成功
}
void display(listlink pp) {
	listnode* ptemp = pp->nest;  //等于首元结点 
	while(ptemp != NULL)   //不是空指针就打印信息
	{
		//pp是头节点
		cout<<ptemp->tempstu.sn<<" "<<ptemp->tempstu.score<<endl;
		ptemp=ptemp->nest;
	} 
}
//按学号升序合并
listlink mergee(listlink p1,listlink p2) {
	//合并后的链表 
	listnode* p3 = new listnode;
	listnode* temp=p3;
	p3->nest=NULL;
	listnode* pt1=p1->nest;
	listnode* pt2=p2->nest;
	//开始合并 
	while(pt1!=NULL && pt2!=NULL) 
	{
		if(pt1->tempstu.sn < pt2->tempstu.sn)
		{
			//将这个数值赋给p3
			p3->nest=pt1;
			pt1=pt1->nest; 
		}
		else
		{
			//将这个数值赋给p3
			p3->nest=pt2;
			pt2=pt2->nest; 
		}
					//更新P3的值 
		p3=p3->nest; 
	}
	//判断
	p3->nest = (pt1 != NULL ? pt1 : pt2); 
	return temp;
}
//确定链表元素
int geshu(listlink p){
	int temp=-1;
	while(p)
	{
		++temp;
		p=p->nest;
	}
	return temp;
} 
 
//单链表冒泡排序
void bubbsort(listlink pt){
	//两轮循环，外轮层数，内轮每个
	//确定个数 
	int pnum = geshu(pt);
	//cout<<"geshiwei---"<<pnum<<endl;
	//临时节点
	listnode* ptemp = pt->nest;   //指向首元结点 
	//n个数据，只需要判断n-1个数据即可 
	for(int i=1;i<=pnum-1;++i)                                                                
	{
		//次数而已
		//将最大的数放到最后面 
		for(int j=1;j<=pnum-i;++j)
		{
			//首元结点与其下一个比较 
			if(ptemp->tempstu.sn > ptemp->nest->tempstu.sn)
			{
				//cout<<"da于"<<endl; 
				//交换位置,只需要交换信息即可（数据域） 
				listnode* ppp = new listnode;
				//先复制好信息 
				ppp->tempstu.sn = ptemp->tempstu.sn;
				ppp->tempstu.score = ptemp->tempstu.score;
				
				ptemp->tempstu.sn =  ptemp->nest->tempstu.sn;
				ptemp->tempstu.score = ptemp->nest->tempstu.score;
				
				ptemp->nest->tempstu.sn = ppp->tempstu.sn;
				ptemp->nest->tempstu.score = ppp->tempstu.score;	 
			}
			else
			{
				//cout<<"xiao于"<<endl;
				//空语句 
			}
			ptemp=ptemp->nest; 
		}
		ptemp = pt->nest;
	}
}
 
int main(){
	//申请一块空间
	//创建头节点p1,p2 
	listnode* p1=(listlink)malloc(sizeof(node));   //头文件cstdlib
	listnode* p2=(listlink)malloc(sizeof(node));
	//头节点指针初始化
	p1->nest=NULL;
	p2->nest=NULL; 
	//读取键盘输入的两个链表的大小
	int n,m;
	cin>>n>>m;
	//创建链表
	creat(p1,n);
	creat(p2,m);
	
	bubbsort(p1);
	bubbsort(p2);
	
	//cout<<"************merge hou**************"<<endl;
	listlink ptemp = mergee(p1,p2);
	display(ptemp); 
	return 0;
}

C/C++，期待与大家一起进步成长！