Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
A:
---------------------------第一遍-------------Merge every two list---------------
public class Solution { public ListNode mergeKLists(ArrayList<ListNode> lists) { if (lists == null || lists.size() == 0) { return null; } // every time, find two shortest list, and merge them ListNode header = new ListNode(Integer.MIN_VALUE); header.next = lists.remove(0); while (!lists.isEmpty()) { // merge the second onto the first ListNode curHeader = new ListNode(0); curHeader.next = lists.remove(0); // add merge two list header = merge2List(header, curHeader); } return header.next; } private ListNode merge2List(ListNode header1, ListNode header2) { ListNode runner1 = header1; while (header2.next != null) { // detach first node of header2 list ListNode tmp = header2.next; header2.next = header2.next.next; // delete tmp node // find runner1 , such that runner1.val < while (runner1.next != null && runner1.next.val < tmp.val) { runner1 = runner1.next; } tmp.next = runner1.next; runner1.next = tmp; runner1 = runner1.next; // point to the next possible value } return header1; } }
其实,网上有个用heap来做的。但是,需要自己动手写comparator,这个正是爷们儿的弱项。需要多写几个。
public class Solution { public ListNode mergeKLists(ListNode[] lists) { if(lists==null || lists.length ==0) return null; ListNode header = new ListNode(0); ListNode tail = header; PriorityQueue<ListNode> minHeap = new PriorityQueue<ListNode>(lists.length,new Comparator<ListNode>(){ public int compare(ListNode a, ListNode b){ return a.val - b.val; } }); for(int i =0;i<lists.length;i++) if(lists[i]!=null) minHeap.add(lists[i]); while( !minHeap.isEmpty()){ ListNode tmp = minHeap.poll(); tail.next = tmp; tail = tail.next; if(tmp.next!=null) minHeap.add(tmp.next); } return header.next; } }
Mistakes:
1: 检查了输入的null,但是没有检查当 size() == 0的时候的情况
2: 由于merge 的时候,我们用了header 来, 所以返回的时候, 原本的list head 可能已经改变了,所以需要给 mergeTwoList() 一个返回值,并 主动设置 i_{th} position of the given ArrayList.
3: 当加入到preNode 和 curNode 之间时, 要记得 重新设置 preNode到 curNode之前。 以保持一致。
4: 汗, 加入到尾部的时候,也要重新设置curNode, 郁闷中~~~~~~~~~~总是犯错
curNode = tmp;
Learned:
No comments:
Post a Comment