# Leetcode: Merge k Sorted Lists

By | 2018 年 7 月 22 日

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

```Input:
[
1->4->5,
1->3->4,
2->6
]
Output: 1->1->2->3->4->4->5->6
```

## Analysis

For this question, first throughs are:

1. build a K-sized min-heap to pick first node from the smallest linked list;

2. Binary merge 2 lists at a time. e.g. for a k=4 lists:
First run, merge the lists indexed 0 and 1 and store in index 0;
Then merge the lists indexed 2 and 3 and store in index 2;
Finally, merge the lists indexed 0 and 2 and store in index 0;
Return the list at index 0;

AS:

Both of them can be done in a O(log(k) * m) time, for m represent the average length of each list. So as the #2 method is more straight forward and doesn’t need to build the heap, I implemented in this way.

## Notes

• The linked list in the source may be empty, got this from test cases;
• Use a temporary `ListNode` instance can simplify the process when merging 2 lists, comparing to just use a pointer (line22 in c++ code);
• Always check break condition when writing `while` loop;
• Draw a table to help figure out the equation of how to calculate `group_base_index` and `group_step` from `step`;

## Solutions

### C++, 16ms beats 99.5%

```/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
private:
// Merge into list1.
// From the test cases, the linked list in the source may be empty.
ListNode* mergeTwoLists(ListNode* pList1, ListNode* pList2) {
if(pList1 == NULL && pList2 == NULL) {
return NULL;
} else if(pList1 == NULL) {
ListNode* temp = pList1;
pList1 = pList2;
pList2 = temp;
}
// so list1 must NOT be empty
while(pList1 && pList2) {
// cout<<pList1->val<<" vs "<<pList2->val<<endl;
ListNode** ppSmall = pList1->val <= pList2->val ? &pList1 : &pList2;
ListNode* pSmallNode = *ppSmall;
pLastNode->next = pSmallNode;
pLastNode = pSmallNode;
*ppSmall = (*ppSmall)->next;
}
pLastNode->next = pList1 ? pList1 : pList2;
}

public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
int size = lists.size();
if(size == 0) {
return NULL;
}
int step = 1;
while(step < size) {
// group_base represents the base index of a group(pair).
// step represents offset from group_base_index to the counterpart.
// group_step represents offset between groups.
int group_step = step * 2;
for(int group_base = 0; group_base + step < size; group_base += group_step) {
// cout<<group_base<<" "<<step<<endl;
// sort group_base and group_base + step, merge into group_base
lists[group_base] = mergeTwoLists(lists[group_base], lists[group_base + step]);
}
step *= 2;
}
return lists[0];
}
};
```