本题要求实现一个函数，将两个链表表示的递增整数序列合并为一个非递减的整数序列。
函数接口定义：
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
C语言实现代码：
#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; } // 有序链表的读取 List Read() { int i, num; scanf("%d", &num); // 创建空节点：链表头节点 List Link = (List)malloc(sizeof(struct Node)); Link->Next = NULL; if (num) { List nextPoint = Link; for (i = 0; i < num; i++) { List point = (List)malloc(sizeof(struct Node)); scanf("%d", &(point->Data)); nextPoint->Next = point; nextPoint = point; } nextPoint->Next = NULL; } return Link; } // 有序链表的输出 void Print(List L) { if (L->Next) { List point = L; while (point->Next) { point = point->Next; printf("%d ", point->Data); } } else { printf("NULL"); } printf("\n"); } // 重点：两个有序链表序列的合并 List Merge(List L1, List L2) { List point1 = L1->Next, point2 = L2->Next; List Link = (List)malloc(sizeof(struct Node)); List linkPoint = Link; while (point1 && point2) { if (point1->Data <= point2->Data) { linkPoint->Next = point1; linkPoint = point1; point1 = point1->Next; } else { linkPoint->Next = point2; linkPoint = point2; point2 = point2->Next; } } linkPoint->Next = point1 ? point1 : point2; L1->Next = NULL; L2->Next = NULL; return Link; }