C语言 有两个单链表LA和LB，其元素均为非递减有序排列，编写一个算法。将他们合并成一个单链表LC

Question

C语言 有两个单链表LA和LB，其元素均为非递减有序排列，编写一个算法。将他们合并成一个单链表LC要求LC是非递增有序数列。新表LC利用原表的储存空间。

Answer 1

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

typedef int Elemtype;
typedef struct node {
Elemtype data;
struct node *next;
}NODE,*LinkList,*pNode;

LinkList GetNewList() {
pNode head = (pNode)malloc(sizeof(NODE));
if(head == NULL) return NULL;
head->data = 0;
head->next = NULL;
return head;
}

LinkList merge(LinkList LA,LinkList LB) {
pNode a,b,c,head;
a = LA;
b = LB;
c = head = GetNewList();
head->data = LA->data + LB->data;
while(a->next && b->next) {
c->next = (pNode)malloc(sizeof(NODE));
if(c->next == NULL) {
printf("内存分配失败！\n");
return NULL;
}
if(a->next->data >= b->next->data) {
c->next->data = a->next->data;
a = a->next;
}
else {
c->next->data = b->next->data;
b = b->next;
}
c = c->next;
}
while(a->next) {
c->next = (pNode)malloc(sizeof(NODE));
if(c->next == NULL) {
printf("内存分配失败！\n");
return NULL;
}
c->next->data = a->next->data;
a = a->next;
c = c->next;
}
while(b->next) {
c->next = (pNode)malloc(sizeof(NODE));
if(c->next == NULL) {
printf("内存分配失败！\n");
return NULL;
}
c->next->data = b->next->data;
b = b->next;
c = c->next;
}
c->next = NULL;
return head;
}

LinkList Creat(LinkList head,int a[],int n) {
int i;
pNode p = head;
head->data = n;
for(i = 0; i < n; ++i) {
p->next = (pNode)malloc(sizeof(NODE));
if(p->next == NULL) {
printf("内存分配失败！\n");
return NULL;
}
p->next->data = a[i];
p = p->next;
}
p->next = NULL;
return head;
}

void Show(LinkList head) {
pNode p = head->next;
while(p) {
printf("%d ",p->data);
p = p->next;
}
printf("\n");
}

int main( ) {
Elemtypea[] = {98,89,86,80,76,69,68,54,50,29};
int m = sizeof(a)/sizeof(a[0]);
Elemtype b[] = {96,85,74,69,68,67,65,60,58};
int n = sizeof(b)/sizeof(b[0]);
LinkList LA = GetNewList();
LA = Creat(LA,a,m);
LinkList LB = GetNewList();
LB = Creat(LB,b,n);
LinkList LC;
printf("LA: ");
Show(LA);
printf("LB: ");
Show(LB);
LC = merge(LA,LB);
printf("LC: ");
Show(LC);
return 0;
}

Answer 2

这个不难哦，可以帮你写！