Question

设计链表合并算法，将两个已排序（升序）的单链表，合并成一个链表而不改变其有序性。用c语言编写。

Answer 1

#include <stdio.h>
#include <malloc.h>
typedef struct node
{
int data;
struct node *next;
}List;
List *create(List *head,int n)//创建链表
{
List *p,*q;
q=(List *)malloc(sizeof(List));
q->data=n;
q->next=NULL;
p=head;
while(p->next!=NULL)p=p->next;
p->next=q;
return head;
}
void print(List *head)//输出链表
{
List *p;
p=head->next;
while(p!=NULL)
{
printf("%d ",p->data);
p=p->next;
}
}
List *LINK(List *head1,List *head2)//连接链表
{
List *p;
p=head1;
while(p->next!=NULL)p=p->next;
p->next=head2->next;
return head1;
}
main()
{
int i;
List *head1,*head2,*link1;
head1=(List *)malloc(sizeof(List));
head1->next=NULL;
head2=(List *)malloc(sizeof(List));
head2->next=NULL;
for(i=1;i<=5;i++)head1=create(head1,i);//输入链表1
printf("链表1:\n");
print(head1);
printf("\n链表2:\n");
for(i=6;i<=10;i++)head2=create(head2,i);//输入链表2
print(head2);
link1=LINK(head1,head2);
printf("\n连接后的链表:\n");
print(link1);
}