# Leetcode 23. Merge k Sorted Lists

## 2. Solution

• Version 1
```/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& 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;
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;
}
}

};```
• Version 2
```/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& 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;
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;
}
}

};```

## Reference

1. https://leetcode.com/problems/merge-k-sorted-lists/description/

440 篇文章56 人订阅

0 条评论