C语言 把两个有序链表合并为一个有序链表(递增)

• 设链表结点结构为Node(int data, Node *next)，typedef Node List，链表均带表头结点。

• 思路是：把list1中的元素看成是集合1，把list2中的元素看成是集合2，把list1头结点（即list1结点）从集合1中脱离下来看成是目标集合的头结点，目标集合开始时是空集，并用last指针始终指向该集合的尾部，然后每次从集合1和集合2中取各自的第一个元素进行比较，较小者从相应集合里脱离，插入到目标集合list1的尾部即last的末尾，并将刚插入的元素作为目标集合list1的新的last，直到集合1为空或集合2为空时结束，最后将未空的集合中的剩余元素链接到last后面即可。
  

• C语言是一种计算机程序设计语言，它既具有高级语言的特点，又具有汇编语言的特点。它由美国贝尔研究所的D.M.Ritchie于1972年推出，1978年后，C语言已先后被移植到大、中、小及微型机上，它可以作为工作系统设计语言，编写系统应用程序，也可以作为应用程序设计语言，编写不依赖计算机硬件的应用程序。

• 它的应用范围广泛，具备很强的数据处理能力，不仅仅是在软件开发上，而且各类科研都需要用到C语言，适于编写系统软件，三维，二维图形和动画，具体应用比如单片机以及嵌入式系统开发。
  

• C语言继续发展，在1982年，很多有识之士和美国国家标准协会为了使这个语言健康地发展下去，决定成立C标准委员会，建立C语言的标准。委员会由硬件厂商，编译器及其他软件工具生产商，软件设计师，顾问，学术界人士，C语言作者和应用程序员组成。

设链表结点结构为Node(int data, Node *next)，typedef Node List，链表均带表头结点。思路是：把list1中的元素看成是集合1，把list2中的元素看成是集合2，把list1头结点（即list1结点）从集合1中脱离下来看成是目标集合的头结点，目标集合开始时是空集，并用last指针始终指向该集合的尾部，然后每次从集合1和集合2中取各自的第一个元素进行比较，较小者从相应集合里脱离，插入到目标集合list1的尾部即last的末尾，并将刚插入的元素作为目标集合list1的新的last，直到集合1为空或集合2为空时结束，最后将未空的集合中的剩余元素链接到last后面即可。

void Merge(List *list1, List *list2) {
/*将有序单链表list2合并到有序单链表list1中，并使list1仍然有序*/
Node *p, *q, *r, *last;
p = list1->next; /*p始终指向集合1的第一个元素*/
q = list2->next; /*q始终指向集合2的第一个元素*/
last = list1; /*将list1看成是目标集合，并从集合1中脱离，并将last始终指向表尾*/
last->next = NULL;
while(p && q) { /*当集合1和集合2都不空时*/
if(p->data < q->data) { /*取两集合中各自的第一个元素进行比较，取其中小者*/
r = p;
p = p->next;
}
else {
r = q;
q = q->next;
}
/*将较小者从相应集合中脱离并插入到目标集合list1的末尾，并使之成为新的last*/
r->next = last->next;
last->next = r;
last = r;
}
/*将未空集合中剩余元素都链接到目标集合list1的last的后面*/
if(p) last->next = p;
else last->next = q;
list2->next = NULL; /*现在的list2为空集了，赋空是为了避免list2的next指针悬空*/
}

#include
#include
#define LEN sizeof(struct link)

struct link //节点
{int num;
struct link *next;
};

struct link *creat() //建立链表
{int a;
struct link *head,*p,*q;
head=(struct link *)malloc(LEN);
head->num=-1;
head->next=NULL;
q=head;
printf("请输入链表(以0结束):\n");
scanf("%d",&a);
while(a)
{p=(struct link *)malloc(LEN);
p->next=NULL;
p->num=a;
q->next=p;
q=p;
scanf("%d",&a);
}
return head;
free(p);free(q);
}

void print_(struct link *q) //输出链表
{printf("您的链表为:");
while(q->next!=NULL)
{printf("%d ",q->next->num);
q=q->next;
}
printf("\n");
}

void sort(struct link *head) //单链表排序
{struct link *p,*q,*r;
int temp;
for(p=head->next;p!=NULL;p=p->next)
{r=p;
for(q=p->next;q!=NULL;q=q->next)
if(q->numnum) r=q;
temp=p->num;
p->num=r->num;
r->num=temp;
}
}

void mix(struct link *p,struct link *q) //合并链表
{struct link *head1,*head2;
head1=p;head2=q;
if(p->next==NULL)
{printf("A表为空!，组合后的链表为B表:\n"); //A表为空时
print_(q);
}
else if(q->next==NULL) //B表为空时
{printf("B表为空!，组合后的链表为A表:\n");
print_(p);
}
else
{p=p->next;q=q->next;
while(p->next!=NULL&&q->next!=NULL) //合并A、B表
{head2->next=q->next;
q->next=p->next;
p->next=q;
p=q->next;
q=head2->next;
}
if(q->next==NULL&&p->next!=NULL) //如果A表长于B表
{q->next=p->next;
p->next=q;
head2->next=NULL;
}
else if(p->next==NULL) //如果A表不长于B表
{p->next=q;
head2->next=NULL;
}
printf("合并后"); //打印合并后的表
sort(head1);
print_(head1);
}

}

void main()
{struct link *A,*B;
printf("A链表:");
A=creat();
printf("B链表:");
B=creat();
mix(A,B);
}

望采纳