This is the 20th day of my participation in the More text Challenge. For more details, see more text Challenge

preface

Force button 23 combined K ascending list as shown below:

You are given an array of linked lists, each of which has been sorted in ascending order.

Please merge all lists into an ascending list and return the merged list.

Example 1:

Input: lists = [].enlighened by [1 4], [2, 6]] output:,1,2,3,4,4,5,6 [1] : list the array is: [1 – > 4 – > 5, 1 – > 3 – > 4, 2 – > 6], merge them into an ordered list is: 1 – > 1 – > 2 – > 3 – > 4 – > 4 – > 5 – > 6

Example 2:

Input: lists = [] Output: []

Example 3:

Input: lists = [[]] Output: []

A, thinking

This is basically the same as combining two ordered lists, but with a slight change of thinking.

The general steps are divided into the following steps:

  1. Get the first node of all the lists
  2. Compare the current values in each list, select the smallest value to add to the new list, and point the nodes that have been added to the list to next
  3. Repeat Step 2

The above steps can actually be implemented using the priority queue in Java. In the implementation process, we only need to pay attention to when to add elements to the priority queue and when to fetch elements.

The priority queue stores a priority-based object, that is, the class that implements the Comparable interface. Note that the Comparable interface is implemented in the priority queue in order to place the elements in place when they are inserted, so that the first element that comes out is the least weighted one (i.e., the lowest value returned by compareTo).

Graphical priority queue

[[1,4,5],[1,3,4],[2,6]] in example 1 is taken as an example here. Red word: indicates the value stored in the priority queue. (take three linked lists as an example, only three priority objects will be stored in the queue.

The initial situation is shown in the figure below

Take out the minimum value 1 and add the next node 4 to the priority queue after the selected node. As shown in the figure below:

Continue to fetch the minimum value 1, and join the selection node after the node 3 into the priority queue. As shown in the figure below:

By analogy, 2 and 3 will be added to the result set in turn, as shown in the figure below:

Later will be 4, 4, 5, 6 can be added to the result set to get the final result 1 – > 1 – > 2 – > 3 – > 4 – > 4 – > 5 – > 6

Second, the implementation

Code implementation

    class Status implements Comparable<Status> {
        int val;
        ListNode node;

        public Status(int val, ListNode node) {
            this.val = val;
            this.node = node;
        }

        // Customize how objects are compared
        @Override
        public int compareTo(Status o) {
            return this.val - o.val; }}/** * Priority queue * tips: official recommendations */
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode ret = new ListNode();
        ListNode temp = ret;
        // Priority queue
        PriorityQueue<Status> queue = new PriorityQueue<>();
        // Add non-empty lists to the priority queue
        for (ListNode node : lists) {
            if(node ! =null)
                // Add to queue
                queue.offer(new Status(node.val, node));
        }
        while(! queue.isEmpty()) {// Find and remove the smallest value in the priority queue
            Status f = queue.poll();
            temp.next = new ListNode(f.val);
            temp = temp.next;
            // If there are still elements in the list, the queue will continue
            if(f.node.next ! =null) {
                queue.offer(newStatus(f.node.next.val, f.node.next)); }}return ret.next;
    }
Copy the code

The test code

    public static void main(String[] args) {
        / / [].enlighened by [1 4], [2, 6]]
        ListNode[] arr = new ListNode[3];
        arr[0] = new ListNode(1.new ListNode(4.new ListNode(5)));
        arr[1] = new ListNode(1.new ListNode(3.new ListNode(4)));
        arr[2] = new ListNode(2.new ListNode(6));
        new Number23().mergeKLists(arr);
    }
Copy the code

The results of

Third, summary

Thank you for seeing the end, it is my great honor to help you ~♥