【数据结构】合并K个有序链表(采用分治法、vector排序法分别实现)

74 阅读 0 评论 49 点赞

我是靠谱客的博主务实芹菜，最近开发中收集的这篇文章主要介绍【数据结构】合并K个有序链表(采用分治法、vector排序法分别实现)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

一、合并K个链表

将n个已经有序的链表，合并成一个链表，使之有序
【1】排序法实现，时间复杂度为O(KNlogKN)
【2】分治法实现，时间复杂度为O(KNlogK)

#include<iostream >
#include<vector>
#include<algorithm>
using namespace std;
struct ListNode
{
	int val;
	ListNode* next;
	ListNode(int x)
		:val(x)
		,next(NULL)
	{}
};

//=====================使用vector进行排序=================
bool cmp(const ListNode *headA, const ListNode* headB)
{
		return headA->val < headB->val ;
}
class solution
{
public:

	ListNode* MergeKLists(vector<ListNode*> &lists)
	{
		vector<ListNode*> node_vec;
		for(int i = 0; i<lists.size(); i++)
		{
			ListNode* head = lists[i];
			while(head)
			{
				node_vec.push_back(head);
				head = head->next ;
			}
		}
		if(node_vec.size() == 0)
		{
			return NULL;
		}

		sort(node_vec.begin(),node_vec.end(),cmp);
		for(int i = 1; i<node_vec.size(); i++)
		{
			node_vec[i-1]->next = node_vec[i];
		}
		node_vec[ node_vec.size() -1 ]->next = NULL;
		return node_vec[0];
	}

};

//=====================使用分治法=================
class solution
{
public:
		ListNode* MergetwoList(ListNode* headA,ListNode* headB)
	{
		ListNode Newhead(0);
		ListNode* ptr = &Newhead;

		while(headA && headB)
		{
			if(headA->val< headB->val )
			{
               ptr->next = headA;
				headA =headA->next ;
			}
			else{
				ptr->next = headB;
				headB = headB->next ;
			}
			ptr = ptr->next ;
		}

		if( headA )
		{
			ptr->next = headA;
		}
		if( headB )
		{
			ptr->next = headB;
		}
		return Newhead.next ;
	}

	ListNode* mergeKList(vector<ListNode*>&lists )
	{
		if(lists.size() == 0)
		{
			return NULL;
		}
		if(lists.size() == 1)
		{
			return lists[0];
		}
		if(lists.size() == 2)
		{
			return MergetwoList( lists[0], lists[1] );//注意这里直接返回，转向两个链表
		}
				
		int mid = lists.size()/2;
		vector<ListNode *> List1 ;
		vector<ListNode *> List2 ;
		
		for(int i = 0; i < mid; i++)
		{
			List1.push_back(lists[i]);
		}

		for( int i = mid; i<lists.size(); i++ )
		{
			List2.push_back(lists[i]);
		}

		ListNode* L1 = mergeKList(List1);
		ListNode* L2 = mergeKList(List2);

		return MergetwoList(L1,L2);
	}
};

int main()
{
	ListNode a(1);
	ListNode b(4);
	ListNode c(6);
	ListNode d(0);
	ListNode e(5);
	ListNode f(11);
	ListNode g(2);
	ListNode h(3);

	a.next = &b;
	b.next = &c;

	d.next = &e;
	e.next = &f;

	g.next = &h;

	solution solve;
	vector< ListNode* > Lists;
	Lists.push_back(&a);
	Lists.push_back(&d);
	Lists.push_back(&g);

	ListNode* head = solve.MergeKLists (Lists);

	while(head)
	{
		printf("%d ,", head->val );
		head = head->next ;
	}

	return 0;
}