[编程入门]链表合并-题解（C语言代码）

解题思路:用尾插法建立带头结点的a,b链表，用a来存储排序后的链表，采用插入排序，分别将a,b链表逐个插入已经有序的a表，释放b头结点！

注意事项:

参考代码:

#include <stdio.h>

//#define INT_MAX 0x7fffffff

//#define INT_MIN 0x80000000

typedef struct Student{

    int num;

    int grade;

}Student;

typedef struct Node{

    Student data;

    struct Node *next;

}Node,*Linklist;

int main()

{

    Linklist a=(Linklist)malloc(sizeof(Node));

    Linklist b=(Linklist)malloc(sizeof(Node));

    Node *p,*s,*r,*pre,*q;

    int n,m,i;

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

    r=a;//用尾插法建立a链表

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

        s=(Node*)malloc(sizeof(Node));

        scanf("%d %d",&s->data.num,&s->data.grade);

        r->next=s;

        r=s;

    }

    r->next=NULL;

    r=b;//用尾插法建立b链表

    for(i=0;i<m;i++){

        s=(Node*)malloc(sizeof(Node));

        scanf("%d %d",&s->data.num,&s->data.grade);

        r->next=s;

        r=s;

    }

    //使用a作为头结点对a进行插入排序

    r->next=NULL;

    p=a->next->next;

    pre=a;

    r=a->next;

    r->next=NULL;

    while(p)

    {

        while(r)//确定插入位置

            if(p->data.num>r->data.num){

                pre=r;

                r=r->next;

            }

            else

                break;

        q=p;//用q摘下节点

        p=p->next;

        q->next=r;

        pre->next=q;

        pre=a;

        r=a->next;

    }

    //将b中的节点插入已经有序的a链表

    p=b->next;

    pre=a;

    r=a->next;

    while(p)

    {

        while(r)//确定插入位置

            if(p->data.num>r->data.num){

                pre=r;

                r=r->next;

            }

            else

                break;

        q=p;//用q摘下节点

        p=p->next;

        q->next=r;

        pre->next=q;

        pre=a;

        r=a->next;

    }

    p=a->next;

    while(p)

    {

        printf("%d %d\n",p->data.num,p->data.grade);

        p=p->next;

    }

    free(b);//释放b节点

}