ListMerge(ListL1,ListL2);
其中List结构定义如下:
typedefstructNode*PtrToNode;
structNode{
ElementTypeData;/*存储结点数据*/
PtrToNodeNext;/*指向下一个结点的指针*/
};
typedefPtrToNodeList;/*定义单链表类型*/
L1和L2是给定的带头结点的单链表,其结点存储的数据是递增有序的;函数Merge要将L1和L2合并为一个非递减的整数序列。应直接使用原序列中的结点,返回归并后的带头结点的链表头指针。
裁判测试程序样例:
#include<stdio.h>
#include<stdlib.h>
typedefintElementType;
typedefstructNode*PtrToNode;
structNode{
ElementTypeData;
PtrToNodeNext;
};
typedefPtrToNodeList;
ListRead();/*细节在此不表*/
voidPrint(ListL);/*细节在此不表;空链表将输出NULL*/
ListMerge(ListL1,ListL2);
intmain()
{
ListL1,L2,L;
L1=Read();
L2=Read();
L=Merge(L1,L2);
Print(L);
Print(L1);
Print(L2);
return0;
}
/*你的代码将被嵌在这里*/
输入样例:
3
135
5
246810
输出样例:
123456810
NULL
NULL
由后面打印出的两个NULL可以看出,这个操作是将L1,L2的节点重新挂在L3的节点上,L1,L2,L3均为头节点,最后实现代码
ListMerge(ListL1,ListL2)
{
Listpa,pb,pc,L;
L=(List)malloc(sizeof(structNode));
pa=L1->Next;//指向pa第一个元素
pb=L2->Next;//指向pb第一个元素
pc=L;
while(pa&&pb)
{
if(pa->Data<=pb->Data)
{
pc->Next=pa;
pc=pa;
pa=pa->Next;
}
else
{
pc->Next=pb;
pc=pb;
pb=pb->Next;
}
}
if(pa)
{
pc->Next=pa;
}
if(pb)
{
pc->Next=pb;
}
L1->Next=NULL;
L2->Next=NULL;
returnL;
}