23. 合并K个升序链表

• 一、题目描述
• 二、示例
• 三、难度
• 四、代码
• • Java版
  • • 4.1 法一：List模拟队列，最小堆
    • 4.2 法二：优先队列

困难

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;


class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 }
public class Solution {

    public ListNode mergeKLists(ListNode[] lists) {
        //头结点
        ListNode mergeList = new ListNode(-1), p = mergeList;
        //存放所有链表中的数
        List list = new ArrayList<>();
        for(int i = 0; i < lists.length; ++i) {
            ListNode q = lists[i];
            while (q != null) {
                list.add(q.val);
                q = q.next;
            }
        }
        // Comparator 接口的 naturalOrder() 方法指定以自然顺序（升序）排序
        // Comparator 接口的 reverseOrder() 方法指定以降序排序
        list.sort(Comparator.naturalOrder());
        for (int i = 0; i < list.size(); ++i) {
            p.next = new ListNode(list.get(i));
            p = p.next;
        }

        return mergeList.next;
    }

    public static void main(String[] args) {
        //l1 -> node1 -> node2
        ListNode node2 = new ListNode(5);
        ListNode node1 = new ListNode(4, node2);
        ListNode l1 = new ListNode(1, node1);

        //l2 -> n1 -> node2
        ListNode n2 = new ListNode(4);
        ListNode n1 = new ListNode(3, n2);
        ListNode l2 = new ListNode(1, n1);

        ListNode n = new ListNode(6);
        ListNode l3 = new ListNode(2, n);

        ListNode[] lists = new ListNode[3];
        lists[0] = l1;
        lists[1] = l2;
        lists[2] = l3;
        ListNode merge = new Solution().mergeKLists(lists);

        while (merge != null) {
            System.out.print(merge.val+" ");
            merge = merge.next;
        }

    }
}

import java.util.Comparator;
import java.util.PriorityQueue;

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

public class Solution {

    public ListNode mergeKLists(ListNode[] lists) {
        //头结点
        ListNode mergeList = new ListNode(-1), p = mergeList;

        
        //先将第一个结点放入堆中   PriorityQueue底层是堆，默认容量11与最小堆,要指定容量需指定排序规则
        //lambda表达式：PriorityQueue queue = new PriorityQueue<>(lists.length, (value1, value2) -> (value1.val - value2.val));
        PriorityQueue queue = new PriorityQueue<>(lists.length, new Comparator() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.val - o2.val;
            }
        });
        for (ListNode list : lists) {
            if (list != null) queue.add(list);
        }

        while (!queue.isEmpty()) {
            // 每次删除小根堆堆顶元素并返回
            ListNode node = queue.poll();
            p.next = node;
            //将该结点后面的结点放入堆中
            if (node.next != null) queue.add(node.next);
            p = p.next;
        }
        return mergeList.next;
    }

    public static void main(String[] args) {
        //l1 -> node1 -> node2
        ListNode node2 = new ListNode(5);
        ListNode node1 = new ListNode(4, node2);
        ListNode l1 = new ListNode(1, node1);

        //l2 -> n1 -> node2
        ListNode n2 = new ListNode(4);
        ListNode n1 = new ListNode(3, n2);
        ListNode l2 = new ListNode(1, n1);

        ListNode n = new ListNode(6);
        ListNode l3 = new ListNode(2, n);

        ListNode[] lists = new ListNode[3];
        lists[0] = l1;
        lists[1] = l2;
        lists[2] = l3;
        ListNode merge = new Solution().mergeKLists(lists);

        while (merge != null) {
            System.out.print(merge.val + " ");
            merge = merge.next;
        }

    }
}