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
Java Solution:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for(ListNode head : lists){
while(head !=null){
minHeap.add(head.val);
head = head.next;
}
}
ListNode dummy = new ListNode(-1);
ListNode result = dummy;
while(!minHeap.isEmpty()){
result.next = new ListNode(minHeap.remove());
result = result.next;
}
return dummy.next;
}
}
No comments:
Post a Comment