链表必学算法（三）：归并法数据结构与算法AuthurWhywait的博客-

 /*归并法：用于合并两个链表*/ /* * SCs in different cases * author: Whywait */ typedef struct node {  Elemtype data; struct node* next; } Lnode; /*case ONE*/  Lnode* merge1(Linklist& LA, Linklist& LB) { // merge two sorted Singly linked lists // LA, LB and the return one ( LC ) all have a head node // all the linklist are sorted in the same way: increasing or decreasing // we assume that all the slists are sorted in an increasing order // KEY: insert in the tail   Lnode* LC = (Lnode*)malloc(sizeof(Lnode));  LC->next = NULL;  Lnode* pa = LA->next, * pb = LB->next, * pc = LC; while (pa && pb) { if (pa->data < pb->data) {    pc->next = pa;    pa = pa->next; } else {    pc->next = pb;    pb = pb->next; }   pc = pc->next; } if (pa) pc->next = pa; if (pb) pc->next = pb; return LC; } /*case TWO*/  Lnode* merge2(Linklist& LA, Linklist& LB) { // merge two sorted Singly linked lists // LA, LB and the return one ( LC ) all have a head node // all the linklist are sorted not in the same way:  //  LA and LB are the same, but LC just the other way // we assume that LA and LB are sorted in an increasing order // KEY: insert in the front   Lnode* LC = (Lnode*)malloc(sizeof(Lnode));  LC->next = NULL;  Lnode* pa = LA->next, * pb = LB->next; while (pa && pb) {   Lnode* temp = NULL; if (pa->data < pb->data) {    temp = pa->next;    pa->next = LC->next;    LC->next = pa;    pa = temp; } else {    temp = pb->next;    pb->next = LC->next;    LC->next = pb;    pb = temp; } } if (pa) pc->next = pa; if (pb) pc->next = pb; return LC; }