[编程入门]链表合并(先用数组输入的数排好序，再传入链表，这样就是合并两个有序的链表，或者定义一个函数给链表节点排序）

解题思路:

注意事项:

参考代码:

使用结构体数组先将输入的数排好序：

#include<stdio.h>
#include<malloc.h>
#include<stdbool.h>
struct Node
{
    int sno;
    int score;
    struct Node *next;
};
void create_list(struct Node **list,int n,struct Node a[n])//建立链表，使用尾插法，保证正序传入数据，这里传递的list是指向list指针的指针，所以在这个函数后面的引用里都要加一个解引符*，注意如果是C++的话可以struct Node *&list，下面的引用也就不用*了
{
    struct Node *s,*r;
    *list=(struct Node*)malloc(sizeof(struct Node));
    r=*list;
    for(int i=0;i<n;i++)
    {
        s=(struct Node*)malloc(sizeof(struct Node));
        s->sno=a[i].sno;
        s->score=a[i].score;
        r->next=s;
        r=s;
    }
    r->next=NULL;
}
void DispList(struct Node*list)//输出合并后的链表
{
    struct Node *p=list->next;
    while(p!=NULL)
    {
        printf("%d %d\n",p->sno,p->score);
        p=p->next;
    }
}
void DestroyList(struct Node **list)//销毁链表，没用上
{
    struct Node *pre=(*list),*p=(*list)->next;
    while(p!=NULL)
    {
        free(pre);
        pre=p;
        p=pre->next;
    }
    free(pre);
}

struct Node *mergerList(struct Node *list1,struct Node *list2)//合并链表
{
    struct Node *merger_list,*p,*q;
    merger_list=(struct Node*)malloc(sizeof(struct Node));
    merger_list->next=NULL;
    p=list1->next;//p被赋予list1的头结点的指针域，也就是链表第一个节点地址
    q=list2->next;
    struct Node *r=merger_list;//r指向合并链表头结点merger_list,用于遍历并构建合并链表
    while(p&&q)//p和q都不为空时进入循环
    {
        if(p->sno<q->sno)//p指向节点数据小，则把p节点地址赋给r的指针域，实现了将p节点连接到合并链表的末尾
        {
            r->next=p;
            r=p;//更新r指针的位置，使其指向当前合并链表的末尾节点，以便下一次循环能将下一节点连接到合并链表的末尾
            p=p->next;//p指向下一个节点
        }
        else
        {
            r->next=q;
            r=q;
            q=q->next;
        }
    }
    if(p)//看剩下哪个指针不为空，还有节点，则将剩余的节点连接到合并链表的末尾
    {
        r->next=p;
    }
    else if(q)
    {
        r->next=q;
    }
    
    return merger_list;
}
int main()
{
	struct Node *list1;
	struct Node *list2;
	int n,m;
	scanf("%d%d",&n,&m);
	struct Node a1[n],a2[m];
	for(int i=0;i<n;i++)
	{
	    scanf("%d%d",&a1[i].sno,&a1[i].score);
	}
	for(int i=0;i<n;i++)
	{
	    for(int j=i+1;j<n;j++)
	    {
	        if(a1[i].sno>a1[j].sno)
	        {
	            struct Node t=a1[i];
	            a1[i]=a1[j];
	            a1[j]=t;
	        }
	    }
	}
    for(int i=0;i<m;i++)
    {
        scanf("%d%d",&a2[i].sno,&a2[i].score);
    }
    for(int i=0;i<m;i++)
    {
        for(int j=i+1;j<m;j++)
        {
            if(a2[i].sno>a2[j].sno)
            {
                struct Node t=a2[i];
                a2[i]=a2[j];
                a2[j]=t;
            }
        }
    }
	create_list(&list1,n,a1);
	create_list(&list2,m,a2);
// 	DispList(list1);
// 	DispList(list2);
	struct Node *merger_list=mergerList(list1,list2);
	DispList(merger_list);
// 	DestroyList(merger_list);
// 	DestroyList(list1);
// 	DestroyList(list2);
	return 0;
}

定义一个函数给链表排序：

#include<stdio.h>
#include<malloc.h>
#include<stdbool.h>
struct Node
{
    int sno;
    int score;
    struct Node *next;
};
void create_list(struct Node **list,int n,int a[][2])
{
    struct Node *s,*r;
    *list=(struct Node*)malloc(sizeof(struct Node));
    r=*list;
    for(int i=0;i<n;i++)
    {
        s=(struct Node*)malloc(sizeof(struct Node));
        s->sno=a[i][0];
        s->score=a[i][1];
        r->next=s;
        r=s;
    }
    r->next=NULL;
}
void DispList(struct Node*list)
{
    struct Node *p=list->next;
    while(p!=NULL)
    {
        printf("%d %d\n",p->sno,p->score);
        p=p->next;
    }
}
void DestroyList(struct Node **list)
{
    struct Node *pre=(*list),*p=(*list)->next;
    while(p!=NULL)
    {
        free(pre);
        pre=p;
        p=pre->next;
    }
    free(pre);
}
void sort_List(struct Node **list) {//对链表进行排序
    struct Node *p, *q, *prev, *temp;
    int swapped;//判断链表里结点是否发生交换
    
    if (*list == NULL)//如果链表为空直接返回
        return;
    
    do {
        swapped = 0;
        p = *list;
        prev = NULL;
        
        while (p->next != NULL) {//可以理解为冒泡排序，p为当前节点，q为下一节点，把最大的节点换到最后一个
            q = p->next;
            
            if (p->sno > q->sno) {
                if (prev != NULL) {
                    prev->next = q;
                } else {
                    *list = q;
                }
                
                p->next = q->next;//把q结点的下一结点的地址赋给p的指针域，也就是p结点的下一结点是此时q节点的下一节点
                q->next = p;//把p的地址赋给q的指针域，也就是现在q的下一节点是p节点，即将q节点插入到p节点的前面，p和q的位置互换了
                
                temp = p;//交换指向的节点
                p = q;
                q = temp;
                swapped = 1;//为1，表示发生了交换
            }
            
            prev = p;//可以记录p节点的前一个节点，以便在交换节点后更新连接关系
            p = p->next;
        }
    } while (swapped);
}

struct Node* mergerList(struct Node* list1, struct Node* list2) {//这里只是简单合并，并未做排序处理
    if (list1 == NULL) {
        return list2;
    }
    if (list2 == NULL) {
        return list1;
    }

    struct Node *merger_list=(struct Node*)malloc(sizeof(struct Node));
    struct Node*current=merger_list;
    struct Node *p=list1->next;
    struct Node *q=list2->next;
    current->next=p;
    while (current->next != NULL) {
        current = current->next;
    }

    current->next = q;
    
    return merger_list;
}

int main()
{
	struct Node *list1;
	struct Node *list2;
	int n,m;
	scanf("%d%d",&n,&m);
	int a1[n][2],a2[m][2];
	for(int i=0;i<n;i++)
	{
	    for(int j=0;j<2;j++)
	    {
	        scanf("%d",&a1[i][j]);
	    }
	}
	for(int i=0;i<m;i++)
	{
	    for(int j=0;j<2;j++)
	    scanf("%d",&a2[i][j]);
	}
	create_list(&list1,n,a1);
	create_list(&list2,m,a2);
// 	DispList(list1);
// 	DispList(list2);
    
	struct Node *merger_list=mergerList(list1,list2);
	sort_List(&merger_list);
	DispList(merger_list);
//	DestroyList(merger_list);
// 	DestroyList(list1);
// 	DestroyList(list2);
	return 0;
}