1, 先将问题简化,合并两个有序链表
首先分析合并两个链表的过程。我们的分析从合并两个链表的头结点开始。链表1的头结点的值小于链表2的头结点的值，因此链表1的头结点将是合并后链表的头结点。如下图所示。
参考:http://www.cnblogs.com/jason2013/articles/4341153.html
使用递归方法,一步步生成头结点,代码如下
递归的要诀是子问题要和父问题完全一样,只是规模变小(每次调用,更小的参数值),
1 List merge(List head1, List head2){ 2 List mergeHead = NULL; 3 if (head1 == NULL) { 4 return head2; 5 } 6 if (head2 == NULL){ 7 return head1; 8 } 9 10 if (head1->item < head2->item){ 11 mergeHead = head1; 12 mergeHead->next = merge(head1->next, head2); 13 }else{ 14 mergeHead = head2; 15 mergeHead->next = merge(head1, head2->next); 16 } 17 return mergeHead; 18 }
2, 当有多个链表时,考虑分治法每两个链表进行合并.
确定父子函数原型,要想使用递归,子问题和父问题必须完全一样(即返回值,参数类型完全一致)
父问题:多个链表
子问题:n/2,...,2个链表,1个链表
递归函数原型List mergeList(int l, int r)
父子问题都是返回一个合并后链表,
使用l,r 两个变量控制问题规模,指定链表个数(快速排序,归并排序都喜欢用这样的两个参数)
将多个链表存放在全局变量vector<List> lists中,简化递归函数.
第9行代码复用前面提到的两个有序链表合并
1 List mergeList(int l, int r){ 2 List u, v; 3 int m = (l + r) / 2; 4 if (l == r) { 5 return lists[l]; 6 } 7 u = mergeList(l, m); 8 v = mergeList(m + 1, r); 9 return merge(u, v); 10 }
3, main 函数
1 int main(void) 2 { 3 int size = 8; 4 int num = 5; 5 ListFactory(size, num); 6 for (int i = 0; i < size; i++){ 7 print(lists[i]); 8 } 9 cout << endl; 10 link t = mergeList(0, size-1); 11 print(t); 12 return 0; 13 }
效果
1->9->17->25->33-> 2->10->18->26->34-> 3->11->19->27->35-> 4->12->20->28->36-> 5->13->21->29->37-> 6->14->22->30->38-> 7->15->23->31->39-> 8->16->24->32->40-> 1->2->3->4->5->6->7->8->9->10->11->12->13->14->15->16->17->18->19->20->21->22->23->24->25->26->27->28->29->30->31->32->33->34->35->36->37->38->39->40->
完整程序
1 #include<iostream> 2 #include<string> 3 #include<vector> 4 using std::cin; 5 using std::cout; 6 using std::endl; 7 using std::string; 8 using std::vector; 9 typedef struct node* link; 10 struct node{ 11 int item; 12 link next; 13 }; 14 typedef link List; 15 vector<List> lists; 16 void print(List list){ 17 while (list != NULL){ 18 cout << list->item<< "->"; 19 list = list->next; 20 } 21 cout << endl; 22 } 23 24 vector<List> ListFactory(int num, int size){ 25 for (int k = 1; k <= num; k++){ 26 link t = (link)malloc(sizeof *t); 27 t->item = k; 28 t->next = t; 29 link x = t; 30 for (int m = k + num; m <= num*size; m = m+num){ 31 x = (x->next = (link)malloc(sizeof *x)); 32 x->item = m; 33 x->next = t; 34 } 35 x->next = NULL; 36 lists.push_back(t); 37 } 38 return lists; 39 } 40 41 List merge(List head1, List head2){ 42 List mergeHead = NULL; 43 if (head1 == NULL) { 44 return head2; 45 } 46 if (head2 == NULL){ 47 return head1; 48 } 49 50 if (head1->item < head2->item){ 51 mergeHead = head1; 52 mergeHead->next = merge(head1->next, head2); 53 }else{ 54 mergeHead = head2; 55 mergeHead->next = merge(head1, head2->next); 56 } 57 return mergeHead; 58 } 59 60 List mergeList(int l, int r){ 61 List u, v; 62 int m = (l + r) / 2; 63 if (l == r) { 64 return lists[l]; 65 } 66 u = mergeList(l, m); 67 v = mergeList(m + 1, r); 68 return merge(u, v); 69 } 70 71 int main(void) 72 { 73 int size = 8; 74 int num = 5; 75 ListFactory(size, num); 76 for (int i = 0; i < size; i++){ 77 print(lists[i]); 78 } 79 cout << endl; 80 link t = mergeList(0, size-1); 81 print(t); 82 return 0; 83 }
原文：http://www.cnblogs.com/hixin/p/7583254.html
