将两个有序链表合并，合并后仍然有序

思路：因为A，B链表中元素递增有序，要使归并后的C也递增有序，可以每次从A、B中挑出最小的元素插入C的尾部，这样循环插入完成后，C也一定是递增有序的。

需要注意的点是，A、B中的元素有可能一个已经全部被插入到C中，而另一个还没插完。

 1 struct LNode{
 2     int data;
 3     LNode *next;
 4 }
 5 
 6 void Merge(LNode *A,LNode *B,LNode *&C)
 7 {
 8     LNode *p = A->next;    // 定义p结点跟踪 A中的结点
 9     LNode *q = B->next;    // 定义q结点跟踪 B中的结点
10 
11     C = A;
12     C->next = NULL;
13     free(B);
14     
15     LNode *r = C;   //  定义一个跟踪结点，永远指向C的终端结点
16     
17     while(p!=NULL&&q!=NULL){
18         if(p->data <= q->data){
19             r->next = p;
20             p = p->next;
21             r = r->next;
22         }else{
23             r->next = q;
24             q = q->next;
25             r = r->next;
26         }
27     }
28 
29     if(p!=NULL) r->next = p;
30     if(q!=NULL) r->next = q;
31 }

如果题这样改：A、B递增有序，合并成C后，C递减有序，怎么做？前面题用的是尾插法插入元素，如果使用头插法插入元素，就可以得到一个递减序列。

 1 struct LNode{
 2     int data;
 3     LNode *next;
 4 }
 5 
 6 void merge(LNode *A,LNode *B,LNode *&C)
 7 {
 8     LNode *p = A->next;
 9     LNode *q = B->next;
10     LNode *s;
11     C = A;  // 使用A的头结点作为C的头结点，然后建立一个空链表
12     C->next= NULL;  
13     free(B);  // 释放B的头结点
14 
15     while(p!=NULL&&q!=NULL){
16         if(p->data<=q->data){
17                 s = p;
18                 p = p->next;
19                 s->next = C->next;
20                 C->next = s;
21                }else{
22                 s = q;
23                 q = q->next;
24                 s->next = C->next;
25                 C->next = s;
26                }
27         }
28         while(p!=NULL){
29             s = p;
30             p = p->next;
31             s->next = C->next;
32             C->next = s;
33         }
34         while(q!=NULL){
35             s = q;
36             q = q->next;
37             s->next = C->next;
38             C->next = s;
39         }
40 }