Merge k Sorted Lists
给k个sorted list, 然后merge. 用一个heap存每个list的当前元素. 然后组一个list.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public ListNode mergeKLists(ListNode[] lists) { if(lists.length == 0 || lists == null) return null; PriorityQueue<ListNode> q = new PriorityQueue<ListNode>(lists.length, new Comparator<ListNode>(){ public int compare(ListNode a, ListNode b) { if(a.val > b.val) return 1; else if(a.val < b.val) return -1; else return 0; } }); for(int i = 0 ; i < lists.length; i++) { if(lists[i] != null) q.add(lists[i]); } ListNode head = new ListNode(0); ListNode p = head; while(!q.isEmpty()){ ListNode node = q.poll(); p.next = node; if(node.next != null) q.add(node.next); p = p.next; } return head.next; } } |