# Convert Hard to Easy, Using Merge Sort, Not Using PiorityQueue

• If merge two List, it is easy, runing O(m+n). So we need to change hard to easy. Divid k to 2, and than conker ( merge), running time is O(knlgn), and no more memory.
Here is my code.

``````class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if(lists == null || lists.length == 0) return null;
int last = lists.length-1;

// repeat until only one list is left
while (last != 0) {
int i = 0, j = last;
// (i, j) forms a pair
while (i < j) {
// merge List i with List j and store
// merged list in List i
lists[i] = mergeTwoLists(lists[i], lists[j]);
// consider next pair
i++; j--;
// If all pairs are merged, update last
if (i >= j) last = j;
}
}

return lists[0];
}

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode p = dummy;
while(l1 != null && l2 != null) {
if(l1.val <= l2.val) {
p.next = l1;
p = l1;
l1 = l1.next;
} else {
p.next = l2;
p = l2;
l2 = l2.next;
}
}

if(l1 != null) p.next = l1;
if(l2 != null) p.next = l2;
return dummy.next;
}
}``````

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