23. Merge k Sorted Lists (Hard)
https://leetcode.com/problems/merge-k-sorted-lists/
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Example:
Input: [ 1->4->5, 1->3->4, 2->6 ] Output: 1->1->2->3->4->4->5->6
Solutions
1.
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists.length == 0) {
return null;
}
ListNode pointer;
// Get the total number of the nodes
int size = 0;
for (int i = 0; i < lists.length; i++) {
pointer = lists[i];
while (pointer != null) {
size += 1;
pointer = pointer.next;
}
}
ListNode dummy = new ListNode(0);
pointer = dummy;
while ((size--) > 0) {
int index = -1;
int min = Integer.MAX_VALUE;
// Walk through the heads of visited stored in lists and find out the minDelete value
// and corresponding index in the list
for (int i = 0; i < lists.length; i++) {
if (lists[i] == null) {
continue;
}
if (lists[i].val < min) {
min = lists[i].val;
index = i;
}
}
pointer.next = lists[index];
pointer = pointer.next;
// Move the header of lists[index] to the next
lists[index] = lists[index].next;
pointer.next = null;
}
return dummy.next;
}
}
2.
class Solution {
// With the help of PriorityQueue, we just pump values into the queue and
// don't have to take the order issue into consideration.
public ListNode mergeKLists(ListNode[] lists) {
if (lists.length == 0) {
return null;
}
// Used to keep the values in ascending order
Queue<ListNode> queue = new PriorityQueue<>(Comparator.comparingInt(o -> o.val));
// insert into priority queue and the elements are sorted automatically
for (int i = 0; i < lists.length; i++) {
if (lists[i] == null) {
continue;
}
ListNode node = lists[i];
while (node != null) {
queue.add(node);
node = node.next;
}
}
ListNode dummy = new ListNode(0);
ListNode pointer = dummy;
// poll all the elements in order and append them to a linked list
while (queue.peek() != null) {
pointer.next = queue.poll();
pointer = pointer.next;
}
pointer.next = null;
return dummy.next;
}
}