两个有序链表序列的合并

#include <stdio.h>
#include <stdlib.h>
typedef int ElementType;
typedef struct Node *PtrToNode;//就是一个数据类型为Node的PtrToNode的指针
struct Node {
ElementType Data;
PtrToNode Next;
};
typedef PtrToNode List;

List Read(); /* 细节在此不表 */
void Print(List L); /* 细节在此不表；空链表将输出NULL */

List Merge(List L1, List L2);

int main()
{
List L1, L2, L;
L1 = Read();
L2 = Read();
L = Merge(L1, L2);
Print(L);
Print(L1);
Print(L2);
system("pause");
}

List Merge(List L1, List L2)//已经固定的链表L1是1,3,5; L2是2,4,6,8,10
{
List L = (List)malloc(sizeof(struct Node));
List pa, pb, pc;
//建立头结点而不能使用L1，L2的头结点是因为后面要将L1，L2置为NULL
pa = L1->Next; pb = L2->Next;//默认L1，L2都是有头结点的
L->Next = NULL;//重新构造一个含有头结点的L
pc = L;
while (pa&&pb)
{
if (pa->Data <= pb->Data)
{
pc->Next = pa;
pa = pa->Next;
pc = pc->Next;
}
else
{
pc->Next = pb;
pb = pb->Next;
pc = pc->Next;
}
}
pc->Next = pa ? pa : pb;
L1->Next = NULL;
L2->Next = NULL;
return L;
}
List Read()
{
int len = 0,num=0;
PtrToNode rear = NULL,h=NULL;
scanf("%d", &len);
if (len == 0)
return NULL;
h = (PtrToNode)malloc(sizeof(struct Node));
h->Next = NULL;//就是一开始设这个表是空表
rear = h;
while(len)
{
PtrToNode p = (PtrToNode)malloc(sizeof(struct Node));
scanf("%d", &(p->Data));
p->Next = NULL;
rear->Next =p;
rear = p;
len--;
}
return h;
}
void Print(List L)
{
if (L->Next == NULL)
{
printf("NULL ");
return;
}
L = L->Next;
while (L != NULL)
{
printf("%d ", L->Data);
L = L->Next;
}
putchar(' ');
}