Linked List Random Node

https://github.com/fishercoder1534/fishercoderLeetcode/blob/master/MEDIUM/src/medium/LinkedListRandomNode.java

Advertisements

Merge K Sorted Lists

https://leetcode.com/problems/merge-k-sorted-lists/

Inspired by this post: https://discuss.leetcode.com/topic/2780/a-java-solution-based-on-priority-queue

Pretty typical Heap problem/solution, although I still don’t understand what k sorted means.


public ListNode mergeKLists(ListNode[] lists) {

Queue<ListNode> heap = new PriorityQueue<ListNode>(new Comparator<ListNode>(){
@Override
public int compare(ListNode o1, ListNode o2) {
if(o1.val > o2.val) return 1;
else if(o1.val < o2.val) return -1;
else return 0;
}
});

for(ListNode node : lists){
if(node != null) heap.offer(node);
}

ListNode head = new ListNode(Integer.MIN_VALUE);
ListNode temp = head;
while(!heap.isEmpty()){
temp.next = heap.poll();
temp = temp.next;
if(temp.next != null) heap.offer(temp.next);
}
return head.next;

}