LinkList MergeSort (LinkList A, LinkList B) { //归并两个带有头结点的递增有序表,为一个带头结点的递减有序表。 ListNode *pa,*pb,*q, *c; pa=A->next; //pa指向A表的开始结点 c=A; c-next=NULL: //取A的头结点给c建立一个空的c表 pb=B->next; //pb指向B的首元素结点 free(B); // 回收B表的头结点空间 while(pa&&pb) { if(pa->data <= pb->data){ q=pa; pa=pa->next; } else { q=pb; pb=pb->next; } q->next=c->next; c->next=q; // 把摘下的结点q作为首结点插入表C中(头插法)(为了C表的递减) } while (pa){ //如果pa表非空,则处理剩下的pa表 q=pa; pa=pa->next; q->next=c->next; c->next=q; } while (pb){ //如果pb表非空,则处理剩下的pb表 q=pb; pb=pb->next; q->next=c->next; c->next=q; } return c; } 该算法的时间复杂度分析: 算法一共有三格while循环,其中第二个第三个只会执行一个。 每个循环做的工作都是对链表中的结点进行扫描处理。 整个算法执行结束后,A和B表的每个结点都被处理了一遍。 所以设A表和B表的长度分别是m和n,则算法的时间复杂度是O(m+n).