区块链技术博客
www.b2bchain.cn

LeetCode算法 —— 合并K个排序链表(归并思想、递归)的讲解

这篇文章主要介绍了LeetCode算法 —— 合并K个排序链表(归并思想、递归)的讲解,通过具体代码讲解7294并且分析了LeetCode算法 —— 合并K个排序链表(归并思想、递归)的讲解的详细步骤与相关技巧,需要的朋友可以参考下

本文实例讲述了LeetCode算法 —— 合并K个排序链表(归并思想、递归)的讲解。分享给大家供大家参考文章查询地址https://www.b2bchain.cn/7294.html。具体如下:

此题使用归并思想解题,步骤类似于归并排序方法

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

示例:

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


代码如下所示:

/**  * Definition for singly-linked list.  * struct ListNode {  *     int val;  *     ListNode *next;  *     ListNode(int x) : val(x), next(NULL) {}  * };  */    class Solution { public: 	ListNode* mergeKLists(vector<ListNode*>& lists) { 		if (lists.empty()) return nullptr;  		// 开始分解数组 		return separation(lists, 0, lists.size() - 1); 	}  private: 	ListNode* merge(ListNode* l1, ListNode* l2) {  		if (l1 == nullptr) return l2; 		else if (l2 == nullptr) return l1;  		ListNode* retList = nullptr; 		ListNode* p = l1, * q = l2;  		p->val > q->val ? (retList = new ListNode(q->val), q = q->next) : 			(retList = new ListNode(p->val), p = p->next);  		ListNode* cur = retList;  		while (p != nullptr && q != nullptr) { 			if (p->val > q->val) { 				cur->next = new ListNode(q->val); 				q = q->next; 			} 			else { 				cur->next = new ListNode(p->val); 				p = p->next; 			}  			cur = cur->next; 		}   		while (p != nullptr) { 			cur->next = new ListNode(p->val); 			cur = cur->next; 			p = p->next; 		}  		while (q != nullptr) { 			cur->next = new ListNode(q->val); 			cur = cur->next; 			q = q->next; 		}  		return retList; 	}  	ListNode* separation(vector<ListNode*>& lists, int left, int right) { 		if (left >= right) return lists[left];  		int mid = (left + right) / 2;  		// 递归分解左边与右边 		ListNode* p = separation(lists, left, mid); 		ListNode* q = separation(lists, mid + 1, right);  		// 开始合并(两个链表的排序合并) 		return merge(p, q); 	} }; 

本文地址https://www.b2bchain.cn/7294.html

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » LeetCode算法 —— 合并K个排序链表(归并思想、递归)的讲解
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们