[LeetCode] 23. Merge k Sorted Listsjava

/**23. Merge k Sorted Lists * @param lists * @return 合并k路有序链表 */ public ListNode mergeKLists(ListNode[] lists) { int n = lists.length; if (n == 0) return null; else if (n == 1) return lists[0]; for (int i=1; i<n; i++) { lists[0] = mergeTwoLists(lists[i], lists[i-1]); } return lists[0]; } public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode ret = new ListNode(-1); ListNode retHead = ret; if (l1 == null && l2 == null) { return null; }else if (l1 == null) { return l2; } else if (l2 == null) { return l1; } while (l1 != null && l2 != null) { if (l1.val <= l2.val) { ret.next = l1; l1 = l1.next; ret = ret.next; } else { ret.next = l2; l2 = l2.next; ret = ret.next; } } if (l1 != null) { ret.next = l1; } if (l2 != null) { ret.next = l2; } return retHead.next; }

//Time limit，

public ListNode mergeKLists(ListNode[] lists) { if (lists == null || lists.length == 0) return null; return merge(lists, 0, lists.length-1); } public ListNode merge(ListNode[] lists, int low, int high) { if (low < high) { int mid = (low+high)/2; ListNode left = merge(lists, low, mid); ListNode right = merge(lists, mid+1, high); return mergeTwoLists(left, right); } return lists[low]; }

归并操作,减小时间复杂度

下面这个方法使用最小堆

public ListNode mergeKLists1(ListNode[] lists) { PriorityQueue<ListNode> heap = new PriorityQueue<ListNode> (10,new Comparator<ListNode>(){ @Override public int compare(ListNode n1, ListNode n2) { return n1.val-n2.val; } }); for(int i=0;i<lists.length;i++) { ListNode node = lists[i]; if(node!=null) { heap.offer(node); } } ListNode head = null; ListNode pre = head; while(heap.size()>0) { ListNode cur = heap.poll(); if(head == null) { head = cur; pre = head; } else { pre.next = cur; } pre = cur; if(cur.next!=null) heap.offer(cur.next); } return head; }

堆 维护一个大小为k的堆，每次取堆顶的最小元素放到结果中，然后读取该元素的下一个元素放入堆中，重新维护好。 因为每个链表是有序的，每次又是去当前k个元素中最小的，所以当所有链表都读完时结束，这个时候所有元素按从小到大放在结果链表中。 这个算法每个元素要读取一次，即是k*n次，然后每次读取元素要把新元素插入堆中要logk的复杂度， 所以总时间复杂度是O(nklogk)。空间复杂度是堆的大小，即为O(k)。