1, 先将问题简化,合并两个有序链表
首先分析合并两个链表的过程。我们的分析从合并两个链表的头结点开始。链表1的头结点的值小于链表2的头结点的值，因此链表1的头结点将是合并后链表的头结点。如下图所示。
参考:
使用递归方法,一步步生成头结点,代码如下
递归的要诀是子问题要和父问题完全一样,只是规模变小(每次调用,更小的参数值),
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 } 
以上图为例,该函数调用结束后:
mergeHead: 1->2->3->4->5->6 原始链表1 : 1->2->3->4->5->6 原始链表2 : 2->3->4->5->6
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 #include2 #include 3 #include 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 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
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 }
后记:
虽然解决了多个有序链表的合并问题,但在解决一道实际OJ题时还是碰到了比较尴尬的问题,题目描述如下:
02-线性结构1 两个有序链表序列的合并（15 分）
本题要求实现一个函数，将两个链表表示的递增整数序列合并为一个非递减的整数序列。
函数接口定义：
List Merge( List L1, List L2 );
其中List结构定义如下：
typedef struct Node *PtrToNode;struct Node { ElementType Data; /* 存储结点数据 */ PtrToNode Next; /* 指向下一个结点的指针 */};typedef PtrToNode List; /* 定义单链表类型 */ L1和L2是给定的带头结点的单链表，其结点存储的数据是递增有序的；函数Merge要将L1和L2合并为一个非递减的整数序列。应直接使用原序列中的结点，返回归并后的链表头指针。
裁判测试程序样例：
#include#include typedef int ElementType;typedef struct Node *PtrToNode;struct Node { ElementType Data; PtrToNode Next;};typedef PtrToNode List;List Read(); /* 细节在此不表 */void Print( List L ); /* 细节在此不表；空链表将输出NULL */List Merge( List L1, List L2 );int main(){ List L1, L2, L; L1 = Read(); L2 = Read(); L = Merge(L1, L2); Print(L); Print(L1); Print(L2); return 0;}/* 你的代码将被嵌在这里 */
输入样例：
31 3 552 4 6 8 10
输出样例：
1 2 3 4 5 6 8 10 NULLNULL
该题和前面的差别在于:
L1和L2是给定的带头结点的单链表，最终要返回归并后的链表头指针。 而且输出结果必须是, 原始链表要置空
1 2 3 4 5 6 8 10 NULLNULL
置空整个链表是需要知道头结点的,而且因为有了头结点,和数据结点存在差异性,递归方法也不太好驾驭了
接口函数实现如下:
版本一:
List Merge(List L1, List L2){ /*struct node head; List mergeHead = &head;*/ //错误写法,函数执行完毕,分配的栈空间会释放,引发空指针. List mergeHead = (List)malloc(sizeof *mergeHead);// 接点作为返回值,要使用malloc分配到堆空间 List merge = mergeHead; if (L1->Next == NULL){ return L2; } if (L1->Next == NULL){ return L1; } List first1 = L1->Next; List first2 = L2->Next; while (first1 != NULL && first2 != NULL){ if (first1->Data < first2->Data){ merge->Next = first1; first1 = first1->Next; }else{ merge->Next = first2; first2 = first2->Next; } merge = merge->Next; } if (first1 == NULL){ //由于链表均为有序,其中一个为空,剩下的数据就无需比较了 merge->Next = first2; } if (first2 == NULL){ merge->Next = first1; } L1->Next = NULL; L2->Next = NULL; return mergeHead;} 结尾加上 L1->Next = NULL;L2->Next = NULL; 基本上可以满足题目的输出,但如果并不加呢? 输出是这样的
原始链表: 1->3->5->7->2->4->6->8-> 合并后:1->2->3->4->5->6->7->8-> 再次打印原始链表:1->2->3->4->5->6->7->8->2->3->4->5->6->7->8->
很明显的看出,这个Merge是有副作用的,改变了原始链表,这不好吧...
版本二:为什么会改变,主要是相加时,没有新建结点,而是复用了原来的链表,把原始链表给改了
稍加修改就好
List Merge(List L1, List L2){ /*struct node head; List mergeHead = &head;*/ //错误写法,函数执行完毕,分配的栈空间会释放,引发空指针. List mergeHead = (List)malloc(sizeof *mergeHead);// 接点作为返回值,要使用malloc分配到堆空间 List merge = mergeHead; if (L1->Next == NULL){ return L2; } if (L1->Next == NULL){ return L1; } List first1 = L1->Next; List first2 = L2->Next; while (first1 != NULL && first2 != NULL){ List temp = (List)malloc(sizeof *temp);// 每次循环创建新结点 if (first1->Data < first2->Data){ temp->Data = first1->Data; merge->Next = temp; first1 = first1->Next; } else{ temp->Data = first2->Data; merge->Next = temp; first2 = first2->Next; } merge = merge->Next; } if (first1 == NULL){ //由于链表均为有序,其中一个为空,剩下的数据就无需比较了 merge->Next = first2; } if (first2 == NULL){ merge->Next = first1; } //L1->Next = NULL; //L2->Next = NULL; return mergeHead;} 版本一 版本二对比如下:
测试的完整程序:
#include#include #include using std::cin;using std::cout;using std::endl;using std::string;using std::vector;typedef struct node* link;struct node{ int Data; link Next;};typedef link List;vector lists;void print(List listHead){ while (listHead->Next != NULL){ listHead = listHead->Next; cout << listHead->Data << "->"; } cout << endl;}List Merge(List L1, List L2){ /*struct node head; List mergeHead = &head;*/ //错误写法,函数执行完毕,分配的栈空间会释放,引发空指针. List mergeHead = (List)malloc(sizeof *mergeHead);// 接点作为返回值,要使用malloc分配到堆空间 List merge = mergeHead; if (L1->Next == NULL){ return L2; } if (L1->Next == NULL){ return L1; } List first1 = L1->Next; List first2 = L2->Next; while (first1 != NULL && first2 != NULL){ if (first1->Data < first2->Data){ merge->Next = first1; first1 = first1->Next; }else{ merge->Next = first2; first2 = first2->Next; } merge = merge->Next; } if (first1 == NULL){ //由于链表均为有序,其中一个为空,剩下的数据就无需比较了 merge->Next = first2; } if (first2 == NULL){ merge->Next = first1; } L1->Next = NULL; L2->Next = NULL; return mergeHead;}int main(void){ link x1, x2,t1,t2; struct node head1, head2; t1 = &head1;//系统随机分配的内存空间做为头结点 t1->Next = t1; x1 = t1; for (int i = 1; i <= 7; i = i + 2){ x1 = (x1->Next = (link)malloc(sizeof *x1)); x1->Data = i; x1->Next = t1; } x1->Next = NULL; print(t1); t2 = &head2; t2->Next = t2; x2 = t2; for (int i = 2; i <= 8; i = i + 2){ x2 = (x2->Next) = (link)malloc(sizeof *x2); x2->Data = i; x2->Next = t2; } x2->Next = NULL; print(t2); link t3 = Merge(t1, t2); print(t3); print(t1); print(t2); return 0;}