close
23. Merge k Sorted Lists
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
就像書上所說,如果結果不注重中間的排序,只在意最小或是最大,可以用heap
這邊就是可以視作先把各個listnode 塞進去,然後一個一個用 min 拉出來
因為是用到heap,time complexity是O(nlogk),space complexity是O(k)
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode mergeKLists(ListNode[] lists) { if (lists==null||lists.length==0) return null; PriorityQueue<ListNode> queue = new PriorityQueue(lists.length, new Comparator<ListNode>(){ public int compare(ListNode a, ListNode b){ return a.val-b.val; } }); for(ListNode list:lists) { if(list != null) queue.add(list); } ListNode dummy = new ListNode(0), tail = dummy; while(!queue.isEmpty()){ tail.next = queue.poll(); tail = tail.next; if(tail.next != null) queue.add(tail.next); } return dummy.next; } }
全站熱搜
留言列表