将两个递增有序的单链表合并成一个非递增有序的单链表。（参考头插法建立单链表算法）
输入描述：先输入第一个单链表个数占一行，下一行输入单链表元素的值。再输入第二个单链表元素个数占一行，下一行输入第二个单链表元素的值。
输出描述：输出合并后的单链表，所有的元素均占一行。
平台会对你编写的代码进行测试：
输入样例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)
{
// 将pa插入到l的后面 和 将pb插入到l的后面
//=========begin1=========
//==========end1==========
}
while(pa)
{
// 将pa剩余的节点插入到l的后面
//==========end2==========
//==========end2==========
}
while(pb)
{
// 将pb剩余的节点插入到l的后面
//==========end3==========
//==========end3==========
}
free(lb);// 释放lb的内存空间
}
int main()
{
Linklist A,B,t;
creatlist(A);//创建链表A
creatlist(B);//创建链表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)
{
// 将pa插入到l的后面 和 将pb插入到l的后面
//=========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)
{
// 将pa剩余的节点插入到l的后面
//==========end2==========
pre = pa->next;
pa->next = l->next;
l->next = pa;
pa = pre;
//==========end2==========
}
while(pb)
{
// 将pb剩余的节点插入到l的后面
//==========end3==========
pre = pb->next;
pb->next = l->next;
l->next = pb;
pb = pre;
//==========end3==========
}
free(lb);// 释放lb的内存空间
}
int main()
{
Linklist A,B,t;
creatlist(A);//创建链表A
creatlist(B);//创建链表B
mergelist(A,B,t);
print(t);
return 0;
}
【以下回答由 GPT 生成】
#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 mergeLinkedList(Linklist &la, Linklist &lb, Linklist &l)
{
Linklist pa, pb, pre, temp;
pa = la->next;
pb = lb->next;
l = la;
la->next = NULL;
while (pa && pb)
{
if (pa->data <= pb->data)
{
temp = pa;
pa = pa->next;
}
else
{
temp = pb;
pb = pb->next;
}
temp->next = l->next;
l->next = temp;
}
while (pa)
{
temp = pa;
pa = pa->next;
temp->next = l->next;
l->next = temp;
}
while (pb)
{
temp = pb;
pb = pb->next;
temp->next = l->next;
l->next = temp;
}
}
int main()
{
Linklist la, lb, l;
// 创建链表la
printf("请输入链表la的节点个数及节点的值：\n");
creatlist(la);
// 创建链表lb
printf("请输入链表lb的节点个数及节点的值：\n");
creatlist(lb);
// 合并链表
mergeLinkedList(la, lb, l);
// 打印合并后的链表
printf("合并后的链表为：\n");
print(l);
return 0;
}
优化问题描述：
问题标签: 数据结构
实现一个函数 mergeLinkedList，该函数能够将两个递增有序的单链表 la 和 lb 合并成一个非递增有序的单链表 l。要求使用头插法建立单链表，并补全给定的代码部分。
#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 mergeLinkedList(Linklist &la, Linklist &lb, Linklist &l)
{
Linklist pa, pb, pre, temp;
pa = la->next;
pb = lb->next;
l = la;
la->next = NULL;
while (pa && pb)
{
if (pa->data <= pb->data)
{
temp = pa;
pa = pa->next;
}
else
{
temp = pb;
pb = pb->next;
}
temp->next = l->next;
l->next = temp;
}
while (pa)
{
temp = pa;
pa = pa->next;
temp->next = l->next;
l->next = temp;
}
while (pb)
{
temp = pb;
pb = pb->next;
temp->next = l->next;
l->next = temp;
}
}
int main()
{
Linklist la, lb, l;
// 创建链表la
printf("请输入链表la的节点个数及节点的值：\n");
creatlist(la);
// 创建链表lb
printf("请输入链表lb的节点个数及节点的值：\n");
creatlist(lb);
// 合并链表
mergeLinkedList(la, lb, l);
// 打印合并后的链表
printf("合并后的链表为：\n");
print(l);
return 0;
}
【相关推荐】