public class Solution {
public ListNode mergeKLists(List<ListNode> lists) {
if (lists == null || lists.size() == 0) {
return null;
}
Queue<ListNode> queue = new PriorityQueue<ListNode>(lists.size(), ListCom);
for (int i = 0; i < lists.size(); i++) {
if (lists.get(i) != null) {
queue.offer(lists.get(i));
}
}
ListNode dummy = new ListNode(0);
ListNode head = dummy;
while (!queue.isEmpty()) {
ListNode cur = queue.poll();
head.next = cur;
if (cur.next != null) {
queue.offer(cur.next);
}
head = head.next;
}
return dummy.next;
}
private Comparator<ListNode> ListCom = new Comparator<ListNode>() {
public int compare(ListNode o1, ListNode o2) {
return o1.val - o2.val;
}
};
}
Thursday, July 24, 2014
Merge k Sorted Lists
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment