leetcode23

解题思路

每个表的第一个元素进最小堆，弹出根之后，根所在的链表更新并维护堆，直到堆为空

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {

    public class minHeap {
        ListNode[] data;
        int len;

        public minHeap(ListNode[] nums) {
            this.data = nums;
            len=data.length;
            buildHeap();
        }
        private void buildHeap() {
            for (int i = 0; i < len; i++) {
                if (data[i] == null) {
                     if (i == len - 1)
                        len--;
                    else if (len > 1 && data[len - 1] == null) {
                        swap(i, len - 2);
                        len -= 2;
                        i--;
                    }
                    else {
                            swap(i, len - 1);
                            len--;
                    }
                }
            }
            System.out.println(len);
            for (int i = (len) / 2 - 1; i >= 0; i--) {
                // 对有孩子结点的元素heapify
                heapify(i);
            }
        }
        private void heapify(int i) {
            // 获取左右结点的数组下标
            int l = left(i);
            int r = right(i);

            // 这是一个临时变量，表示 跟结点、左结点、右结点中最小的值的结点的下标
            int smallest = i;

            // 存在左结点，且左结点的值小于根结点的值
            if (l < len && data[l].val < data[i].val)
                smallest = l;

            // 存在右结点，且右结点的值小于以上比较的较小值
            if (r < len && data[r].val < data[smallest].val)
                smallest = r;

            // 左右结点的值都大于根节点，直接return，不做任何操作
            if (i == smallest)
                return;

            // 交换根节点和左右结点中最小的那个值，把根节点的值替换下去
            swap(i, smallest);

            // 由于替换后左右子树会被影响，所以要对受影响的子树再进行heapify
            heapify(smallest);
        }

        private void swap(int i, int j) {
            ListNode temp = data[i];
            data[i] = data[j];
            data[j] = temp;
        }

        private int right(int i) {
            return (i + 1) << 1;
        }

        // 获取左结点的数组下标
        private int left(int i) {
            return ((i + 1) << 1) - 1;
        }

        public int getRoot() {
            return data[0].val;
        }

        // 替换根元素，并重新heapify
        public void setRoot() {
            if (data[0].next != null)
                data[0] = data[0].next;
            else {
                swap(0,len-1);
                len--;
            }
           heapify(0);
        }
    
    }
    public ListNode mergeKLists(ListNode[] lists) {
        var heap=new minHeap(lists);
              if(heap.len<1)
            return null;
        ListNode l = new ListNode(heap.getRoot());
        heap.setRoot();
        ListNode first=l;
        ListNode temp;
        while (heap.len>0){
            temp=new ListNode(heap.getRoot());
            l.next=temp;
            l=temp;
            heap.setRoot();
        }
        return first;
    }
}