23. 合并K个升序链表

合并K个升序链表

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

一、题目描述

二、示例

三、难度

困难

四、代码 Java版 4.1 法一：List模拟队列，最小堆

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

/**
 * @author Kidd
 * @create 2022-04-24 14:00
 */
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;
        }

    }
}

4.2 法二：优先队列

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;

        /*
            public PriorityQueue(int initialCapacity) {
                this(initialCapacity, null);
            }

            java8 lambda表达式
            // 1. 不需要参数,返回值为 5
            () -> 5

            // 2. 接收一个参数(数字类型),返回其2倍的值
            x -> 2 * x

            // 3. 接受2个参数(数字),并返回他们的差值
            (x, y) -> x – y

            // 4. 接收2个int型整数,返回他们的和
            (int x, int y) -> x + y

            // 5. 接受一个 string 对象,并在控制台打印,不返回任何值(看起来像是返回void)
            (String s) -> System.out.print(s)
         */
        //先将第一个结点放入堆中   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;
        }

    }
}