Merge k Sorted Lists

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;
}