23. Merge k Sorted Lists

[Shawngbk]

与21题相关，就是运用merge排序来做。

D daniel123 Reputation: 2 minHeap: time - O(nlog(k)), space - O(k), n is total number of all the listnode, k is the length of lists

public ListNode mergeKLists(ListNode[] lists) { if (lists == null || lists.length == 0) { return null; } return heap(lists); } private ListNode heap(ListNode[] lists) { PriorityQueue pq = new PriorityQueue<>(new Comparator() { public int compare(ListNode a, ListNode b) { return a.val - b.val; } }); for (ListNode head : lists) { if (head != null) pq.offer(head); } ListNode res = new ListNode(0); ListNode resHead = res; while (!pq.isEmpty()) { ListNode cur = pq.poll(); res.next = cur; res = res.next; if (cur.next != null) { pq.offer(cur.next); } } return resHead.next; }

like mergeSort(recursion): time-O(vlog(k)), space- O(log(k)), v is average length of a list, k is length of lists

/**

• 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; } return helper(lists, 0, lists.length-1); }

  private ListNode helper(ListNode[] lists, int start, int end) { if(start == end) { return lists[start]; } int mid = (start + end) / 2; ListNode left = helper(lists, start, mid); ListNode right = helper(lists, mid+1, end); return merge2Lists(left, right); }

  private ListNode merge2Lists(ListNode left, ListNode right) { ListNode head = new ListNode(0); ListNode flag = head; while(left != null || right != null) { if(left != null && right != null) { if(left.val < right.val) { flag.next = left; left = left.next; } else { flag.next = right; right = right.next; } flag = flag.next; } if(left == null) { flag.next = right; break; } if(right == null) { flag.next = left; break; } } return head.next; } }

[Shawngbk]

考