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