23. 合并K个排序链表(C++)

题目详情
合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:
输入: [  
1->4->5,  
1->3->4,  
2->6
]
输出: 1->1->2->3->4->4->5->6

——题目难度:困难


 

思路
在 21. 合并两个有序链表这道题的基础上进行多次两个链表的排序结合工作即可。

-下面代码 
 

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
	ListNode* mergeTwoLists(ListNode* p1, ListNode* p2) {
		if(!p1) return p2;
		if(!p2) return p1;
		
	if(p2->val >= p1->val){
		p1->next = mergeTwoLists(p1->next,p2);
		  return p1;
	}else{
		p2->next = mergeTwoLists(p1,p2->next);
		return p2;
	}
}

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.size()==0) return NULL;
        
        ListNode* head = lists[0];
        for(int i=1;i<lists.size();i++)
        {
    		head = mergeTwoLists(head,lists[i]);
        }
        
        return head;
    }
        	
};

结果

最后

以上就是无心紫菜为你收集整理的23. 合并K个排序链表(C++)的全部内容，希望文章能够帮你解决23. 合并K个排序链表(C++)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。