23. 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
Solution
(1) Java
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) {
return null;
}
PriorityQueue<ListNode> q = new PriorityQueue<>(lists.length, new Comparator<ListNode>() {
public int compare(ListNode n1, ListNode n2) {
return n1.val-n2.val;
}
});
ListNode head = null;
ListNode prev = null;
for (ListNode node : lists) {
if (node != null) {
q.offer(node);
}
}
while (q.size() > 0) {
if (head == null) {
head = q.poll();
prev = head;
if (head.next != null) {
q.offer(head.next);
}
} else {
ListNode node = q.poll();
prev.next = node;
prev = node;
if (node.next != null) {
q.offer(node.next);
}
}
}
return head;
}
}
(2) Python
class Solution(object):
def mergeKLists(self, lists):
"""
:type lists: List[ListNode]
:rtype: ListNode
"""
if not lists:
return None
q = []
for node in lists:
if node:
q.append((node.val, node))
heapq.heapify(q)
head = None
prev = None
while q:
if not head:
val, nt = heapq.heappop(q)
head = nt
prev = head
if head.next:
heapq.heappush(q, (head.next.val, head.next))
else:
val,nt = heapq.heappop(q)
prev.next = nt
prev = nt
if nt.next:
heapq.heappush(q, (nt.next.val, nt.next))
return head
(3) Scala
/**
* Definition for singly-linked list.
* class ListNode(var _x: Int = 0) {
* var next: ListNode = null
* var x: Int = _x
* }
*/
object Solution {
def mergeKLists(lists: Array[ListNode]): ListNode = {
def comp(node: ListNode) = -node.x
import scala.collection.mutable.PriorityQueue
var q: PriorityQueue[ListNode] = PriorityQueue()(Ordering.by(comp))
for (node<-lists) {
if (node != null) {
q.enqueue(node)
}
}
var head: ListNode = null
var prev: ListNode = head
while (q.size > 0) {
val node: ListNode = q.dequeue()
if (head == null) {
head = node
prev = node
if (node.next != null) {
q.enqueue(node.next)
}
} else {
prev.next = node
prev = node
if (node.next != null) {
q.enqueue(node.next)
}
}
}
return head
}
}