# Got TEL using merge sort, which is O(nlogn), any one have better solution

• ``````/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *mergeKLists(vector<ListNode *> &lists) {

int n = lists.size();
int groupNum = n/2;
int i;
ListNode* result;
ListNode* index1;
ListNode* index2;
ListNode* previous;
ListNode* tempIndex;

vector<ListNode*> tempList;
vector<ListNode*> sorted;
vector<ListNode*> temp;
sorted = lists;

if(lists.size()==0) return NULL;
if(lists.size()==1) return lists[0];

while(groupNum>=1)
{
for(i=0;i<groupNum;i++)
{
index1 = sorted[2*i];
index2 = sorted[2*i+1];

if(!index1 && !index2)
{
continue;
}
else if(index1 && !index2)
{
tempList.push_back(index1);
continue;
}
else if(!index1 && index2)
{
tempList.push_back(index2);
continue;
}

previous = NULL;

while(index1 && index2)
{
if(index1->val > index2->val)
{
if(previous)
{
previous->next = index2;
}
else
{
}

tempIndex = index2->next;
index2->next = index1;
index2 = tempIndex;

previous = index2;
}
else
{
previous = index1;
index1= index1->next;
}
}

if(index2)
{
previous->next = index2;
}

}

//change groupNum
if(sorted.size()-2*groupNum >0) tempList.push_back(sorted[sorted.size()-1]);

temp = sorted;
sorted = tempList;
tempList = temp;
tempList.clear();

groupNum = sorted.size()/2;
}

result = sorted[0];
return result;
}
};``````

• Thanks for your post. I just updated your post with correct code format, hope you will pay attention next time.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.