有序表的合并
已知线性表La 和Lb中的数据元素按值非递减有序排列,现要求将La和Lb归并为一个新的线性表Lc,且Lc中的数据元素仍按值非递减有序排列。

La=(1 ,7, 8)
Lb=(2, 4, 6, 8, 10, 11)
Lc=(1, 2, 4, 6, 7 , 8, 8, 10, 11)

0.新建一个链表
新建一个空表C，直接在A和B中每次选取最小值插入到C中，复杂度O(A.length+B.length)，但是需要新开辟一个空表比较占用内存。

void MergeList_Sq(SqList LA,SqList LB,SqList &LC){ 
    pa = LA.elem;  
    pb = LB.elem;     //指针pa和pb的初值分别指向两个表的第一个元素 
    LC.length = LA.length+LB.length;          //新表长度为待合并两表的长度之和 
    LC.elem = new ElemType[LC.length];        //为合并后的新表分配一个数组空间 
    pc = LC.elem;                                 //指针pc指向新表的第一个元素 
    pa_last = LA.elem+LA.length-1;     //指针pa_last指向LA表的最后一个元素 
    pb_last = LB.elem+LB.length-1;     //指针pb_last指向LB表的最后一个元素 
    while(pa <= pa_last && pb <= pb_last){      //两个表都非空 
        if(*pa <= *pb) *pc++ = *pa++;            //依次“摘取”两表中值较小的结点      
        else *pc++ = *pb++;   
    } 
    //此时a,b 之中一定有一个表为空
    while(pb <= pb_last)  *pc++ = *pb++;          //LB表已到达表尾
    while(pa <= pa_last)  *pc++ = *pa++;          //LA表已到达表尾 
}//MergeList_Sq 

1.直接合并

只建一个新结点，相当于尾插法的end尾结点，而不是创建一个新链表，结点Pc每次指向A/B中最小值的结点，把两个链表连在一起（B连到A上面），不需要新开辟一个链表浪费空间，时间复杂度和上面的一样，都是暴力循环。

void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc){
   pa=La->next;  pb=Lb->next;
   pc=Lc=La;                    //用La的头结点作为Lc的头结点 
   while(pa && pb){
      if(pa->data<=pb->data){ pc->next=pa;pc=pa;pa=pa->next;}
      else{pc->next=pb; pc=pb; pb=pb->next;}
   pc->next=pa?pa:pb;      //插入剩余段  
   delete Lb;                     //释放Lb的头结点}