Question

求助c语言大神 链表合并并排序

已有a、b两个链表，每个链表中的节点包括学号、成绩，且a、b两个链表中的节点均按照学号升序排列。要求把两个链表合并，按照学号升序排列并输出。

输入格式

第一行有两个用空格隔开的整数n和m，分别表示a和b两个链表中的节点个数。保证n和m均不超过100。
之后的n行每行有两个用空格隔开的整数，分别表示一个学生的学号和成绩。
最后的m行每行有两个用空格隔开的整数，分别表示一个学生的学号和成绩。
输入保证所有的节点中学号各不相同。

输出

合并之后升序排列的链表，每行两个用空格隔开的整数，分别表示一个学生的学号和成绩。
#include <stdio.h>
#include <stdlib.h>

struct node {
int num;
int score;
struct node * next;
};

int main()
{
int n, m, i;
struct node *heada, *taila, *headb, *tailb, *head, *tail, *p;
heada = taila = headb = tailb = NULL;

printf("Please input n m:[1-100]\n");
scanf("%d%d", &n, &m);
/* 读入a链表中的n个学生信息 */
printf("Please input %d students' numbers and scores:\n", n);
for (i = 0; i < n; i++)
{
p = (struct node *)malloc(sizeof(struct node));
scanf("%d%d", &p->num, &p->score);
if (heada == NULL)
{
heada = taila = p;
}
else
{
taila->next = p;
taila = p;
}
}
taila->next = NULL;
/* 读入b链表中的m个学生信息 */
printf("Please input %d students' numbers and scores:\n", m);
for (i = 0;i < m;i++)
{
p = (struct node *)malloc(sizeof(struct node));
scanf("%d%d", &p->num, &p->score);
if (headb == NULL)
{
headb = tailb = p;
}
else
{
tailb->next = p;
tailb = p;
}
}
tailb->next = NULL;

printf("Output:\nThe result is:\n");
/* 合并两个链表 */
/******start******/

/******end******/
/* 将合并后的链表进行输出 */
p = head;
while (p != NULL)
{
printf("%d %d\n", p->num, p->score);
p = p->next;
}
return 0;
}

Answer 1

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

struct node
{
    int num;
    int score;
    struct node * next;
};

int main()
{
    int n, m, i;
    struct node *heada, *taila, *headb, *tailb, *head, *tail, *p;
    heada = taila = headb = tailb = NULL;

    printf("Please input n m:[1-100]\n");
    scanf("%d%d", &n, &m);
    /* 读入a链表中的n个学生信息 */
    printf("Please input %d students' numbers and scores:\n", n);
    for (i = 0; i < n; i++)
    {
        p = (struct node *)malloc(sizeof(struct node));
        scanf("%d%d", &p->num, &p->score);
        if (heada == NULL)
        {
            heada = taila = p;
        }
        else
        {
            taila->next = p;
            taila = p;
        }
    }
    taila->next = NULL;
    /* 读入b链表中的m个学生信息 */
    printf("Please input %d students' numbers and scores:\n", m);
    for (i = 0; i < m; i++)
    {
        p = (struct node *)malloc(sizeof(struct node));
        scanf("%d%d", &p->num, &p->score);
        if (headb == NULL)
        {
            headb = tailb = p;
        }
        else
        {
            tailb->next = p;
            tailb = p;
        }
    }
    tailb->next = NULL;

    printf("Output:\nThe result is:\n");
    /* 合并两个链表 */
    /******start******/
    if(taila->num < headb->num)    /*如果a尾部节点学号比b头部节点学号小，直接把a的尾部和b的头部挂接即可，下同*/
    {
        head = heada;
        tail = tailb;
        taila->next = headb;
    }
    else if(heada->num > tailb->num)
    {
        head = headb;
        tail = taila;
        tailb->next = heada;
    }
    else
    {
        head = tail = NULL;
        while(heada && headb)
        {
            if(heada->num < headb->num)
            {
                if(head == NULL)
                {
                    head = heada;
                    tail = heada;
                }
                else
                {
                    tail->next = heada;
                    tail = heada;
                }
                heada = heada->next;
            }
            else
            {
                if(head == NULL)
                {
                    head = headb;
                    tail = headb;
                }
                else
                {
                    tail->next = headb;
                    tail = headb;
                }
                headb = headb->next;
            }
        }
        if(heada)    /*如果还是有剩余队列a，剩下的必定是最大的，放在队尾*/
        {
            tail->next = heada;
            tail = taila;
        }
        if(headb)
        {
            tail->next = headb;
            tail = tailb;
        }
    }

    /******end******/
    /* 将合并后的链表进行输出 */
    p = head;
    while (p != NULL)
    {
        printf("%d %d\n", p->num, p->score);
        p = p->next;
    }
    return 0;
}

Answer 2

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

typedef struct node {
	int num;
	int score;
	struct node *next;
}*LinkList,*pNode,LNode;

LinkList getEmptyList() {
	LinkList head = (pNode)malloc(sizeof(LNode));
	head->next = NULL;
	head->next = 0;
	head->score = 0;
	return head;
}

int insertNode(LinkList head, LNode node) {
	pNode p = head;
	pNode q;
	while(p->next) {
		if(p->next->num == node.num) {
			printf("重复的学号:%d\n",node.num);
			return 0;
		}
		if(p->next->num > node.num) {
			q = (pNode)malloc(sizeof(LNode));
			q->num = node.num;
			q->score = node.score;
			q->next = p->next;
			p->next = q;
			return 1;
		}
		p = p->next;
	}
	q = (pNode)malloc(sizeof(LNode));
	q->num = node.num;
	q->score = node.score;
	p->next = q;
	q->next = NULL;
	return 1;
}

void mergeList(LinkList LA, LinkList LB, LinkList LC) {
	pNode p;
	for(p = LA->next; p; p = p->next)
		insertNode(LC,*p);
	for(p = LB->next; p; p = p->next)
		insertNode(LC,*p);
}

void show(LinkList head) {
	pNode p = head->next;
	while(p) {
		printf("%d\t%d\n",p->num,p->score);
		p = p->next;
	}
}

int main() {
	int n, m, i;
	LinkList LA = getEmptyList();
	LinkList LB = getEmptyList();
	LinkList LC = getEmptyList();
	LNode node;
	printf("n m\n");
	scanf("%d%d", &n, &m);
	/* 读入a链表中的n个学生信息 */
	printf("输入%d组数据:\n", n);
	for(i = 0; i < n; i++) {
		scanf("%d%d", &node.num,&node.score);
		insertNode(LA,node);
	}
	printf("输入%d组数据:\n", m);
	for(i = 0; i < m; i++) {
		scanf("%d%d", &node.num,&node.score);
		insertNode(LB,node);
	}
	printf("LA:\n");
	show(LA);
	printf("LB:\n");
	show(LB);
	mergeList(LA,LB,LC);
	printf("LC:\n");
	show(LC);
	return 0;
}

Answer 3

if (taila == NULL)
        head=tailb;
    else
    {
        if (tailb != NULL)
        {
            for (tail = taila; tail->next != NULL; tail = tail->next);
            tail->next = tailb; /*遍历taila中节点直到尾节点*/
        }
head=taila;
    }