题解-链表合并

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

typedef struct Stu{

int id;

int sore;

struct Stu *next;

}node;

node *creat(int n); //创建生成链表函数 

node *add(node *student1,node *student2);//创建合并链表函数 

void sort(node *student);//创建排序函数

void print_f(node *student);//创建输出函数 

int main()

{

int n,m;

scanf("%d%d",&n,&m);

// 创建两个链表 

node *student1=creat(n);

node *student2=creat(m);

// 合并两个链表 

node *student=add(student1,student2);

sort(student);

print_f(student);

return 0;

}

node *creat(int n)

{

//生成一个头结点,申请内存空间 

node *head=(node*)malloc(sizeof(node));

if(head==NULL)

return NULL;

//初始化链表

head->id=-1;

head->sore=-1;

head->next=NULL;

node *temp=head;//让temp指针指向head

for(int i=0;i<n;i++)

{

node *new_node=(node*)malloc(sizeof(node));//创建一个结点指针，并申请内存

if(new_node==NULL)

return 0;

scanf("%d %d",&new_node->id,&new_node->sore);

//用尾插入法

new_node->next=NULL;

temp->next=new_node;

//然后然temp指针向后移动一位

temp=new_node; 

}

return head;

}

//合并两个链表 

node *add(node *student1,node *student2)

{

   //首先判断两个链表起码有一个链表不为空

   if(student1==NULL||student2==NULL)

   return NULL;

   //首先找到第一个链表的尾节点 

   node *p1=student1;

   while(p1->next!=NULL)

   {

    p1=p1->next;

   }

   //让第一个链表的尾结点和第二个链表的首结节连接（注意是首结点）

   node *p2=student2;

   p1->next=p2->next;

   //释放第二个链表的头结点

    free(p2);

   return student1; 

}

//将合并好的链表排序

void sort(node *student)

{

if(student==NULL)

return;

node *ii,*jj;

node temp;

ii=NULL;

jj=NULL;

//用选择排序法

for(ii=student->next;ii->next!=NULL;ii=ii->next) //除去头结点

{

for(jj=ii->next;jj!=NULL;jj=jj->next)

{

//数据域要交换，指针域也要交换

if(ii->id>jj->id)

{

   temp=*ii;

   *ii=*jj;

   *jj=temp;

   temp.next=ii->next;

   ii->next=jj->next;

   jj->next=temp.next;

} 

}

  } 

}

void print_f(node *student)

{

if(student==NULL||student->next==NULL)

{

return ;

}

node *p=student->next;//让p指针指向student的首结点 

while(p!=NULL)

{

printf("%d %d\n",p->id,p->sore);

p=p->next;

}

}