Leetcode|Leetcode 23. Merge k Sorted Lists
【Leetcode|Leetcode 23. Merge k Sorted Lists】文章作者：Tyan
博客：noahsnail.com|CSDN|
1. Description 
文章图片
Merge k Sorted Lists 2. Solution
- Version 1
/**
* Definition for singly-linked list.
* struct ListNode {
*int val;
*ListNode *next;
*ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeKLists(vector& lists) {
int size = lists.size();
if(size == 0) {
return NULL;
}
ListNode* result = lists[0];
for(int i = 1;
i < size;
i++) {
result = mergeTwoLists(result, lists[i]);
}
return result;
}private:
ListNode* mergeTwoLists(ListNode* first, ListNode* second) {
ListNode* ptrFirst = first;
ListNode* ptrSecond = second;
ListNode* head = new ListNode(0);
ListNode* current = head;
while(ptrFirst && ptrSecond) {
if(ptrFirst->val > ptrSecond->val) {
current->next = ptrSecond;
ptrSecond = ptrSecond->next;
}
else {
current->next = ptrFirst;
ptrFirst = ptrFirst->next;
}
current = current->next;
}
if(ptrFirst) {
current->next = ptrFirst;
}
if(ptrSecond) {
current->next = ptrSecond;
}
return head->next;
}};
- Version 2
/**
* Definition for singly-linked list.
* struct ListNode {
*int val;
*ListNode *next;
*ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeKLists(vector& lists) {
int size = lists.size();
if(size == 0) {
return NULL;
}
ListNode* result = NULL;
while(lists.size() != 1) {
ListNode * l1 = lists.back();
lists.pop_back();
ListNode * l2 = lists.back();
lists.pop_back();
result = mergeTwoLists(l1, l2);
lists.insert(lists.begin(), result);
}
return lists[0];
}private:
ListNode* mergeTwoLists(ListNode* first, ListNode* second) {
ListNode* ptrFirst = first;
ListNode* ptrSecond = second;
ListNode* head = new ListNode(0);
ListNode* current = head;
while(ptrFirst && ptrSecond) {
if(ptrFirst->val > ptrSecond->val) {
current->next = ptrSecond;
ptrSecond = ptrSecond->next;
}
else {
current->next = ptrFirst;
ptrFirst = ptrFirst->next;
}
current = current->next;
}
if(ptrFirst) {
current->next = ptrFirst;
}
if(ptrSecond) {
current->next = ptrSecond;
}
return head->next;
}};
Reference
- https://leetcode.com/problems/merge-k-sorted-lists/description/
推荐阅读
- 【Leetcode/Python】001-Two|【Leetcode/Python】001-Two Sum
- leetcode|leetcode 92. 反转链表 II
- 二叉树路径节点关键值和等于目标值（LeetCode--112&LeetCode--113）
- LeetCode算法题-11.|LeetCode算法题-11. 盛最多水的容器（Swift）
- LeetCode（03）Longest|LeetCode（03）Longest Substring Without Repeating Characters
- Leetcode|Leetcode No.198打家劫舍
- [leetcode数组系列]1两数之和
- 数据结构和算法|LeetCode 的正确使用方式
- leetcode|今天开始记录自己的力扣之路
- LeetCode|LeetCode 876. 链表的中间结点