https://leetcode.com/problems/merge-k-sorted-lists/
写不动解释了,
手撸小顶堆的解法,网上一大堆直接用PriorityQueue的解法
public ListNode mergeKLists(ListNode[] lists) {
ListNode newNode = new ListNode(-1);
ListNode res = newNode;
int len = lists.length - 1;//小顶堆的长度
int[] heap = new int[lists.length];
HashMap<Integer, List<ListNode>> map = new HashMap<Integer, List<ListNode>>();
for (int i = 0; i < lists.length; i++) {
ListNode tmp = lists[i];
if (tmp == null) {
//有空链表
len--;
continue;
}
//k-v, listNode的值和对应的idx
List<ListNode> tmpList = map.get(tmp.val);
if (tmpList == null) {
tmpList = new ArrayList<ListNode>();
}
tmpList.add(lists[i]);
map.put(tmp.val, tmpList);
heap[i] = tmp.val;
}
if(map.size() == 0){
return null;
}
while (len >= 0) {
buildHeap(heap, len);
//把最小的放到新的Node队列尾
ListNode tmpNode = new ListNode(heap[0]);
newNode.next = tmpNode;
newNode = newNode.next;
//找出刚才找出的值对应的ListNode
List<ListNode> tt = map.get(heap[0]);
ListNode nowNode = tt.get(0);
//删除这个List中的这个ListNode
tt.remove(0);
//对应更新map
if (tt.isEmpty()) {
map.remove(heap[0]);
} else {
map.put(heap[0], tt);
}
//处理nowNode
nowNode = nowNode.next;
if (nowNode == null) {
//其中有一个List已经找完
heap[0] = heap[len];//把heap的最后一个提到第一个来,保证index在0~len是一个小顶堆
len--;
if(len < 0){
break;
}
buildHeap(heap, len);
continue;
}
int tmpVal = nowNode.val;
List<ListNode> ll = map.get(tmpVal);
if (ll == null) {
ll = new ArrayList<ListNode>();
}
ll.add(nowNode);
heap[0] = tmpVal;
map.put(heap[0], ll);
buildHeap(heap, len);
}
return res.next;
}
private void buildHeap(int[] nums, int end) {
for (int i = (end - 1) / 2; i >= 0; i--) {
heapHelper(nums, i, end);
}
}
private void heapHelper(int[] nums, int idx, int end) {
// if (idx > (end - 1) / 2) {
// return;
// }
for (int i = idx; i >= 0; i--) {
int left = 2 * idx + 1;
int right = 2 * idx + 2;
int min = idx;
if (left <= end && nums[min] > nums[left]) {
min = left;
}
if (right <= end && nums[min] > nums[right]) {
min = right;
}
if (min != idx) {
swap(nums, min, idx);
heapHelper(nums, min, end);
}
}
}
//-------------------------------------------
//-------------------------------------------
//-------------------------------------------
//-------------------------------------------
public void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
直接用PriorityQueue的方法
参考:https://zhuanlan.zhihu.com/p/33050219
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) return null;
PriorityQueue<ListNode> queue = new PriorityQueue<>(lists.length, (a,b) -> a.val -b.val);// 重写了compare函数,按照链表们的头部进行升序排序Override the compare function, sort by the head of the lists in ascending order
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
for (ListNode list : lists) {
if (list != null) {
queue.add(list);
}
}
while (! queue.isEmpty()) {
cur.next = queue.poll();
cur =cur.next;
if (cur.next != null) {
queue.add(cur.next);
}
}
return dummy.next;
}