23. Merge k Sorted Lists

Hard

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6

Solution：
1)初始化一个pre变量，pre.next = min;
2) 先拿到最小堆的堆顶，只要链条还没比较完而且堆里还有ListNode没有比较，就进入循环。堆顶是当前节点，将pre.next = min;
3）如果当前节点的下个节点不为空，就把这个节点放到堆顶，然后调整堆。
4）设置pre为当前节点，当前节点min为堆顶。
每次开始循环前，当前节点已经设置好。

    public ListNode mergeKLists(ListNode[] lists) {
     int k = lists.length;
     ListNode[] heap = new ListNode[k];
     
     for(int i = 0; i < k; i++) {
      heapInsert(heap,lists[i],i);
     }

     ListNode pre = null;
     ListNode min = heap[0];
     ListNode head = min;
//     pre = min;
     int heapSize = k;
     //当最小堆的堆顶弹掉，左子树和右子树分别是最小堆
     while(min!=null&& heapSize > 0) {
      if(pre!=null) {
       pre.next = min;
      }
      
      if(min.next != null) {
       heap[0] = min.next;
       min.next = null;
       heapify(heap,0,heapSize);
       pre = min;
       min = heap[0];
      }else {
       heapSize--;
       heap[0] = heap[heapSize];
       min.next = null;
       pre = min;
       heapify(heap,0,heapSize);
       min = heap[0];
      }
     }
     
  return head;
        
    }
    
    public void heapInsert(ListNode[] heap, ListNode toAddNode, int index) {
     heap[index] = toAddNode;
     while(index>=0) {
      int parent = (index - 1)/2;
      ListNode node = heap[index];
      ListNode pnode = heap[parent];
      if(heap[parent].val > heap[index].val) {
       swap(heap,index, parent);
       index = parent;
      }else {
       break;
      }
     }
    }
    public void heapify(ListNode[] heap, int index, int size) {
     int left = index * 2 + 1;
     int right = index * 2 + 2;
     int smallest = index;
     while(left < size) {
      if(heap[left].val < heap[index].val) {
       smallest = left;
      }
      if(right < size && heap[right].val < heap[smallest].val) {
       smallest = right;
      }
      if(smallest == index) {
       break;
      }else {
       swap(heap,smallest, index);
       index = smallest;
          left = index * 2 + 1;
          right = index * 2 + 2;
      }
      
     }
     
    }
    public void swap(ListNode[] heap, int i, int j) {
     ListNode temp = heap[i];
     heap[i] = heap[j];
     heap[j] = temp;
    }