将两个递增有序的单链表合并成一个非递增有序的单链表。（参考头插法建立单链表算法）
输入描述：先输入第一个单链表个数占一行，下一行输入单链表元素的值。再输入第二个单链表元素个数占一行，下一行输入第二个单链表元素的值。
输出描述：输出合并后的单链表，所有的元素均占一行。
输入样例1：
5
1 3 5 7 9
3
2 3 4
输出样例1：
9 7 5 4 3 3 2 1
输入样例2：
4
4 5 6 7
3
1 2 3
输出样例2：
7 6 5 4 3 2 1
补全如下代码
#include<stdio.h>
#include<malloc.h>
typedef struct LNode
{
int data;
struct LNode *next;
}LNode,*Linklist;
void creatlist(Linklist &l)
{
Linklist p,q;int m=0;
l=(Linklist)malloc(sizeof(LNode));
l->next=NULL;
p=l;
scanf("%d",&m);
for(int i=0;i<m;i++){
q=(Linklist)malloc(sizeof(LNode));
q->next=NULL;
scanf("%d",&q->data);
p->next=q;
p=q;
}
}
void print(Linklist l)
{
Linklist p;
p=l->next;
while(p)
{
printf("%d ",p->data);
p=p->next;
}
}
void mergelist(Linklist &la,Linklist &lb,Linklist &l)
{
Linklist pa,pb,pre;
pa=la->next;
pb=lb->next;
l=la;
la->next=NULL;
while(pa&&pb)
{
//=========begin1=========
//==========end1==========
}
while(pa)
{
//==========end2==========
//==========end2==========
}
while(pb)
{
//==========end3==========
//==========end3==========
}
free(lb);
}
int main()
{
Linklist A,B,t;
creatlist(A);
creatlist(B);
mergelist(A,B,t);
print(t);
return 0;
}
代码如下：
#include<stdio.h>
#include<malloc.h>
typedef struct LNode
{
int data;
struct LNode *next;
}LNode,*Linklist;
void creatlist(Linklist &l)
{
Linklist p,q;int m=0;
l=(Linklist)malloc(sizeof(LNode));
l->next=NULL;
p=l;
scanf("%d",&m);
for(int i=0;i<m;i++){
q=(Linklist)malloc(sizeof(LNode));
q->next=NULL;
scanf("%d",&q->data);
p->next=q;
p=q;
}
}
void print(Linklist l)
{
Linklist p;
p=l->next;
while(p)
{
printf("%d ",p->data);
p=p->next;
}
}
void mergelist(Linklist &la,Linklist &lb,Linklist &l)
{
Linklist pa,pb,pre;
pa=la->next;
pb=lb->next;
l=la;
la->next=NULL;
while(pa&&pb)
{
//=========begin1=========
if(pa->data < pb->data)
{
pre = pa->next;
pa->next = l->next;
l->next = pa;
pa = pre;
}else
{
pre = pb->next;
pb->next = l->next;
l->next = pb;
pb = pre;
}
//==========end1==========
}
while(pa)
{
//==========end2==========
pre = pa->next;
pa->next = l->next;
l->next = pa;
pa = pre;
//==========end2==========
}
while(pb)
{
//==========end3==========
pre = pb->next;
pb->next = l->next;
l->next = pb;
pb = pre;
//==========end3==========
}
free(lb);
}
int main()
{
Linklist A,B,t;
creatlist(A);
creatlist(B);
mergelist(A,B,t);
print(t);
return 0;
}
【以下回答由 GPT 生成】
void mergelist(Linklist &la, Linklist &lb, Linklist &l){
Linklist pa, pb, pre;
pa = la->next;
pb = lb->next;
l = la;
la->next = NULL;
while(pa && pb){
if(pa->data >= pb->data){
pre = pa;
pa = pa->next;
pre->next = l->next;
l->next = pre;
}else{
pre = pb;
pb = pb->next;
pre->next = l->next;
l->next = pre;
}
}
while(pa){
pre = pa;
pa = pa->next;
pre->next = l->next;
l->next = pre;
}
while(pb){
pre = pb;
pb = pb->next;
pre->next = l->next;
l->next = pre;
}
}
上述代码中的mergelist函数是将两个递增有序链表合并为一个非递增有序链表的实现。在循环中，通过比较两个链表当前节点的数据，将较大的节点插入到新链表的头部。最后，如果其中一个链表还有剩余元素，则直接将剩余元素添加到新链表的头部。这样就能实现将两个递增有序链表合并为一个非递增有序链表的功能。
【相关推荐】