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

爱被打了一巴掌 2022-05-15 06:08 109阅读 0赞

## 一、合并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;
    }

![70][]

[70]: /images/20220515/30adbea0e959490a93cb86e9b415a71f.png