已知k個(gè)已排序鏈表頭節(jié)點(diǎn)指針，將這k個(gè)鏈表合并，合并后仍為有序的 ，返回合并后的頭節(jié)點(diǎn)
如下三個(gè)鏈表：

合并后的結(jié)果如下：

方法一（STL sort算法進(jìn)行排序）：

1. 先將輸入的排序鏈表插入一個(gè)迭代器中，vector數(shù)組中國(guó)呢
2. 直接對(duì)數(shù)組中的鏈表節(jié)點(diǎn)進(jìn)行按值排序即可

實(shí)現(xiàn)算法如下,最終實(shí)現(xiàn)源碼見(jiàn)文末:

bool cmp(Data *A, Data *B) {return A->data < B->data;
}
Data *merge_list2(vector<Data*> &list) {/*如果傳入的鏈表數(shù)組大小為0，則返回空*/if(list.size() == 0) {return NULL;}/*傳入的數(shù)組大小為1，則返回第一個(gè)鏈表頭節(jié)點(diǎn)*/if(list.size() == 1) {return list[0];}/*遍歷所有的鏈表，并將每個(gè)鏈表的所有節(jié)點(diǎn)插入一個(gè)vector中*/vector<Data*> result;for (int i = 0;i < list.size(); ++i) {while(list[i]) {result.push_back(list[i]);list[i] = list[i] -> next;}}/*對(duì)vector按照升序排序，其中排序規(guī)則可以由cmp函數(shù)自定義指定*/sort(result.begin(),result.end(),cmp);return result[0];
}

方法二（分治歸并）：
使用合并兩個(gè)有序鏈表的實(shí)現(xiàn)，對(duì)所有鏈表進(jìn)行兩兩合并至僅剩下兩個(gè)，最后合并最后的兩個(gè)鏈表,關(guān)于合并兩個(gè)有序鏈表可以參考C語(yǔ)言的有序單鏈表合并
這里面的思想就是分而治之，將整體分割為一個(gè)個(gè)獨(dú)立的個(gè)體分別處理，再進(jìn)行最后的整合。
算法使用遞歸方式實(shí)現(xiàn)如下，最終實(shí)現(xiàn)源碼見(jiàn)文末:

Data *merge_list(vector<Data *> &list) {/*如果傳入的鏈表數(shù)組大小為0，則返回空*/if(list.size() == 0) {return NULL;}/*傳入的數(shù)組大小為1，則返回第一個(gè)鏈表頭節(jié)點(diǎn)*/if (list.size() == 1) {return list[0];}/*將鏈表分為兩部分，分別放入不同的鏈表結(jié)構(gòu)*/int mid = list.size() / 2;int i;vector <Data *> sub_list1,sub_list2;for (i = 0; i < mid; ++i) {sub_list1.push_back(list[i]);}for (i = mid; i < list.size(); ++i) {sub_list2.push_back(list[i]);}/*分別進(jìn)行遞歸處理*/Data *list1 = merge_list(sub_list1);Data *list2 = merge_list(sub_list2);/*將以上兩部分處理的最終結(jié)果返回，進(jìn)行兩個(gè)有序鏈表的合并*/return merge_two_list(list1,list2);
}

以上兩個(gè)過(guò)程實(shí)現(xiàn)代碼如下：

#include <iostream>
#include <algorithm>
#include <vector>
#include <stdio.h>using namespace std;typedef struct LinkList {int data;struct LinkList *next;
}Data;
/*打印鏈表節(jié)點(diǎn)數(shù)值*/
void print_list(Data *head) {while (head) {printf("%d ",head->data);head = head -> next;}printf("\n");
}
/*尾插法創(chuàng)建鏈表*/
Data *insert_tail(Data *head, int n) {head = (Data *)malloc(sizeof(Data));head->next = NULL;Data *r = head;while(n--) {Data *p = (Data *)malloc(sizeof(Data));int data;scanf("%d", &data);p->data = data;r->next = p;r = p;p->next = NULL;}return head->next;
}
/*合并兩個(gè)有序鏈表算法實(shí)現(xiàn)*/
Data *merge_two_list(Data *headA, Data *headB) {Data p;p.data = 0;p.next = NULL;Data *result = &p;while (headA && headB) {if (headA->data < headB->data) {result->next = headA;headA = headA->next;} else {result->next = headB;headB = headB ->next;} result = result -> next;}if (headA == NULL) {result ->next = headB;}    if (headB == NULL) {result ->next = headA;}return p.next;
}
/*分治歸并算法實(shí)現(xiàn)的鏈表合并*/
Data *merge_list(vector<Data *> &list) {if(list.size() == 0) {return NULL;}if (list.size() == 1) {return list[0];}int mid = list.size() / 2;int i;vector <Data *> sub_list1,sub_list2;for (i = 0; i < mid; ++i) {sub_list1.push_back(list[i]);}for (i = mid; i < list.size(); ++i) {sub_list2.push_back(list[i]);}Data *list1 = merge_list(sub_list1);Data *list2 = merge_list(sub_list2);return merge_two_list(list1,list2);
}
/*控制排序的規(guī)則，當(dāng)前為升序*/
bool cmp(Data *A, Data *B) {return A->data < B->data;
}
/*排序算法實(shí)現(xiàn)鏈表的鏈表*/
Data *merge_list2(vector<Data*> &list) {if(list.size() == 0) {return NULL;}if(list.size() == 1) {return list[0];}vector<Data*> result;for (int i = 0;i < list.size(); ++i) {while(list[i]) {result.push_back(list[i]);list[i] = list[i] -> next;}}sort(result.begin(),result.end(),cmp);return result[0];
}int main() {vector<Data*> list;printf("input the num of the construct list \n");int num;scanf("%d",&num);for (int i = 0; i < num; ++i){Data *p;printf("construct the %d list:\n",i+1);list.push_back(insert_tail(p,3)); //尾插法構(gòu)造三個(gè)節(jié)點(diǎn)的鏈表}printf("merget the mulity list with method 1 is \n");Data *result = merge_list(list);print_list(result);printf("merge the mulity list with method 2 is \n");Data *result2 = merge_list2(list);print_list(result2);return 0;
}

最終輸出如下

input the num of the construct list 
4  
construct the 1 list:
1 2 3
construct the 2 list:
3 4 5
construct the 3 list:
4 5 6
construct the 4 list:
6 7 8
merget the mulity list with method 1 is 
1 2 3 3 4 4 5 5 6 6 7 8 
merget the mulity list with method 2 is 
1 2 3 3 4 4 5 5 6 6 7 8 

總結(jié)

以上是生活随笔為你收集整理的C++的多个有序链表合并的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。