I just solved LeetCode hard problem #23: Merge k sorted Lists, which is asked in interviews for a lot of companies, including Facebook, Uber, Google and you name it! It can look intimidating but...
Hint: It's too easy if you can think of the right Data Structure for solving the problem.
Here's my O(lg n) solution where n is the cardinality of all the elements combined in all lists:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
ListNode dummy = new ListNode(-1);
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for(ListNode list : lists) {
while (list != null) {
minHeap.add(list.val);
list = list.next;
}
}
ListNode head = dummy;
while (!minHeap.isEmpty()) {
head.next = new ListNode(minHeap.remove());
head = head.next;
}
return dummy.next;
}
}
Feel free to share your thoughts below!
No comments:
Post a Comment