9.20号练习

本题要求实现一个函数，将两个链表表示的递增整数序列合并为一个非递减的整数序列。

函数接口定义：
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合并为一个非递减的整数序列。应直接使用原序列中的结点，返回归并后的带头结点的链表头指针。

 1 List Merge(List L1,List L2){
 2     List L,head;
 3     L=head=(List)malloc(sizeof(struct Node));
 4     if(!L1->Next && !L2->Next){
 5         L->Next=NULL;
 6         return L;
 7     }
 8     List i1=L1;
 9     List i2=L2;
10     L1=L1->Next;
11     L2=L2->Next;
12     i1->Next=NULL;
13     i2->Next=NULL;
14     if(L1->Data<L2->Data){
15         L->Next=L1;
16         L1=L1->Next;
17         L=L->Next;
18     }
19     else{
20         L->Next=L2;
21         L2=L2->Next;
22         L=L->Next;
23     }
24     while(L1||L2){
25         if(L1&&L2){
26             if(L1->Data<L2->Data){
27                 L->Next=L1;
28                 L1=L1->Next;
29             }else{
30                 L->Next=L2;
31                 L2=L2->Next;
32             }
33         }
34         else if(!L1){
35         L->Next=L2;
36         L2=L2->Next;
37         }
38         else if(!L2){
39             L->Next=L1;
40             L1=L1->Next;
41         }
42         L=L->Next;
43         L->Next=NULL;
44     }
45     return head;
46 }