JunyiCode
4/23/2020 - 3:29 AM

## 23. Merge k Sorted Lists

21 follow up 5 solutions 也算是top k问题

``````/*
⭐️⭐️⭐️
Time complexity:
O(Nlogk) where k is the number of linked lists.

Space complexity:
O(n) Creating a new linked list costs O(n) space.
O(k) The code above present applies in-place method which cost O(1) space.

*/

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

Comparator<ListNode> cmp;
cmp = new Comparator<ListNode>() {
@Override
public int compare(ListNode o1,ListNode o2){
/*
if (o1.val < o2.val)
return -1;
else if (o1.val == o2.val)
return 0;
else
return 1;
*/
return o1.val - o2.val;
}
};

PriorityQueue<ListNode> queue = new PriorityQueue<ListNode>(cmp);

/*
PriorityQueue<ListNode> queue = new PriorityQueue<ListNode>(new Comparator<ListNode>() {
@Override
public int compare(ListNode o1,ListNode o2){
return o1.val - o2.val;
}
});
*/

ListNode dummy = new ListNode(0);
ListNode cur = dummy;

for (ListNode node : lists) {
if (node != null) {
}
}

while(!queue.isEmpty()) {
cur.next = queue.poll();
cur = cur.next;
if (cur.next != null) {
}
}

return dummy.next;
}
}``````
``````/*
⭐️⭐️
Time is O(nlogk), merge takes O(n) time and partition takes O(logk) time
*/

public class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) return null;
return sort(lists, 0, lists.length - 1);
}

private ListNode sort(ListNode[] lists, int lo, int hi) {
if (lo >= hi) return lists[lo];
int mid = lo + (hi - lo) / 2;
ListNode l1 = sort(lists, lo, mid);
ListNode l2 = sort(lists, mid + 1, hi);
return mergeTwoLists(l1, l2);
}

private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) return l2;
if (l2 == null) return l1;
if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
}``````
``````/*
⭐️
Time:  O(kn)
Space: O(n)
*/

class Solution {
public ListNode mergeKLists(ListNode[] lists) {
List<Integer> l = new ArrayList<Integer>();
int min_index = 0;

while(true) {
boolean isVisitedAll = true;
int min = Integer.MAX_VALUE;
for(int i = 0; i < lists.length; i++) {
if(lists[i] != null) {
isVisitedAll = false;
if(lists[i].val < min) {
min = lists[i].val;
min_index = i;
//lists[min_index] = lists[min_index].next; 不能写到这里因为当前这个不一定是最小的
}
}
}

if(isVisitedAll) {
break;
}

ListNode newNode = new ListNode(min);
cur.next = newNode;
cur = cur.next;
lists[min_index] = lists[min_index].next;
}

cur.next = null;
}
}``````
``````/*
Time:  O(nlogn)
Space: O(n)
*/

class Solution {
public ListNode mergeKLists(ListNode[] lists) {
List<Integer> l = new ArrayList<Integer>();
for (ListNode ln : lists) {
while (ln != null) {
ln = ln.next;
}
}

Collections.sort(l);

for (int i : l) {
ListNode t = new ListNode(i);
h.next = t;
h = h.next;
}
h.next = null;
}
}``````
``````
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if(lists.length==1){
return lists[0];
}
if(lists.length==0){
return null;
}
for (int i = 2; i < lists.length; i++) {
}
}

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

return ans.next;
}
}
``````