C++的多个有序链表合并

首页 > C++的多个有序链表合并

C++的多个有序链表合并

已知k个已排序链表头节点指针，将这k个链表合并，合并后仍为有序的，返回合并后的头节点

如下三个链表：

在这里插入图片描述

合并后的结果如下：

方法一（STL sort算法进行排序）：

先将输入的排序链表插入一个迭代器中，vector数组中国呢
直接对数组中的链表节点进行按值排序即可

实现算法如下,最终实现源码见文末:

bool cmp(Data *A, Data *B) { return A->data < B->data;
}
Data *merge_list2(vector<Data*> &list) { /*如果传入的链表数组大小为0，则返回空*/if(list.size() == 0) { return NULL;}/*传入的数组大小为1，则返回第一个链表头节点*/if(list.size() == 1) { return list[0];}/*遍历所有的链表，并将每个链表的所有节点插入一个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;}}/*对vector按照升序排序，其中排序规则可以由cmp函数自定义指定*/sort(result.begin(),result.end(),cmp);return result[0];
}

方法二（分治归并）：

使用合并两个有序链表的实现，对所有链表进行两两合并至仅剩下两个，最后合并最后的两个链表,关于合并两个有序链表可以参考C语言的有序单链表合并

这里面的思想就是分而治之，将整体分割为一个个独立的个体分别处理，再进行最后的整合。

算法使用递归方式实现如下，最终实现源码见文末:

Data *merge_list(vector<Data *> &list) { /*如果传入的链表数组大小为0，则返回空*/if(list.size() == 0) { return NULL;}/*传入的数组大小为1，则返回第一个链表头节点*/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);
}

以上两个过程实现代码如下：

#include 
#include 
#include 
#include using namespace std;typedef struct LinkList { int data;struct LinkList *next;
}Data;
/*打印链表节点数值*/
void print_list(Data *head) { while (head) { printf("%d ",head->data);head = head -> next;}printf("
");
}
/*尾插法创建链表*/
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;
}
/*合并两个有序链表算法实现*/
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;
}
/*分治归并算法实现的链表合并*/
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);
}
/*控制排序的规则，当前为升序*/
bool cmp(Data *A, Data *B) { return A->data < B->data;
}
/*排序算法实现链表的链表*/
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 
");int num;scanf("%d",&num);for (int i = 0; i < num; ++i){ Data *p;printf("construct the %d list:
",i+1);list.push_back(insert_tail(p,3)); //尾插法构造三个节点的链表}printf("merget the mulity list with method 1 is 
");Data *result = merge_list(list);print_list(result);printf("merge the mulity list with method 2 is 
");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

C++的多个有序链表合并

更多相关：

list_for_each_safe

Nested Mappings

链式表的按序号查找

Linux篇---ftp服务器的搭建

python制作统计图_刻意练习11：Python描述统计、简单统计图形

python3socket非阻塞_利用Python中SocketServer 实现客户端与服务器间非阻塞通信

剑指offer：面试题37. 序列化二叉树

sd.js 2.0封装：更加简化请求传参内容

sd.js帮助您简化繁重的获取数据、存储数据（CRUD）骚操作（吐槽~在安卓9.0以下或者IOS10.X以下手机端H5页面不支持，在这两

剑指offer--day07