本题要求实现一个函数，将两个链表表示的递增整数序列合并为一个非递减的整数序列。
函数接口定义：
List Merge( List L1, List L2 );
其中List结构定义如下：
typedef struct Node PtrToNode; struct Node { ElementType Data; / 存储结点数据 / PtrToNode Next; / 指向下一个结点的指针 / }; typedef PtrToNode List; / 定义单链表类型 */
L1和L2是给定的带头结点的单链表，其结点存储的数据是递增有序的；函数Merge要将L1和L2合并为一个非递减的整数序列。应直接使用原序列中的结点，返回归并后的带头结点的链表头指针。
裁判测试程序样例：
#include <stdio.h> #include <stdlib.h> typedef int ElementType; typedef struct 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); return 0; } /* 你的代码将被嵌在这里 */输入样例：
3 1 3 5 5 2 4 6 8 10
输出样例：
1 2 3 4 5 6 8 10 NULL NULL
/* 两个有序链表序列的合并 */ #include <stdio.h> #include <stdlib.h> typedef int ElementType; typedef struct Node *PtrToNode; struct Node { ElementType Data; PtrToNode Next; }; typedef PtrToNode List; List Read(); void Print( List L ); void Attach (ElementType number,List *p1); 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); return 0; } List Read() { List head; int x,n; scanf("%d",&n); head=(List )malloc(sizeof(struct Node)); head->Next=NULL; if(n) { List r=head; for(int i=0;i<n;i++) { List p=(List )malloc(sizeof(struct Node)); scanf("%d",&(p->Data)); r->Next=p; r=p; } r->Next=NULL; } return head; } List Merge( List L1, List L2 ) { List p=(List )malloc(sizeof(struct Node)); List r=p; List t1=L1->Next; List t2=L2->Next; while(t1&&t2) { if(t1->Data>t2->Data) { r->Next=t2; r=t2; t2=t2->Next; } else { r->Next=t1; r=t1; t1=t1->Next; } } r->Next=t1 ? t1 :t2; L1->Next=NULL; L2->Next=NULL; return p; } void Print( List L ) { List p=L->Next; if(p) { while(p) { printf("%d ",p->Data); p=p->Next; } printf("\n"); } else printf("NULL\n"); }