【刷力扣】23. 合并 K 个升序链表（dummy节点技巧 + 分治思维 + 优先队列）

一、合并升序链表问题

• 合并升序链表问题是链表专题的经典问题。
  • 我们需要掌握：dummy节点的技巧。
• 23. 合并 K 个升序链表在21. 合并两个有序链表基础上，还需要掌握如下技能：
  • （1）分治思维。我们将合并K个升序链表转化为多次合并2个升序链表。归并排序也用到了分治思维。
  • （2）优先队列（小根堆/大根堆）。维护一个序列的最小/大值。

二、题目：21. 合并两个有序链表

1、掌握dummy节点的技巧

• 在创建新链表时，定义一个dummy节点，在如下代码中，res便是dummy节点，因此，最后答案是：return res.next;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        }

        if (list2 == null) {
            return list1;
        }

        ListNode p1 = list1, p2 = list2, res = new ListNode(), p = res;
        while (p1 != null && p2 != null) {
            if (p1.val <= p2.val) {
                p.next = p1;
                p1 = p1.next;
            } else {
                p.next = p2;
                p2 = p2.next;
            }
            p = p.next;
        }

        if (p1 == null) {
            p.next = p2;
        }

        if (p2 == null) {
            p.next = p1;
        }

        return res.next;
    }
}

三、题目：23. 合并 K 个升序链表

1、分治思维

1.1 插曲

• 看到这道题，首先想到的是合并2个升序链表。p1指向链表list1，p2指向链表list2。关键步骤是：

if (p1.val <= p2.val) {
    ...
} else {
    ...
}

• 很显然，k个升序链表需要想其他办法去求最小值对应的节点。好久没刷算法了。不记得咋求了…（忘记优先队列了，要补上这个技术点）
• 但想到了归并排序。所以，可以将k个升序链表转成2个升序链表的问题。

1.2 代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) return null;
        return merge(lists, 0, lists.length - 1);
    }

    private ListNode merge(ListNode[] lists, int i, int j) {
        if (i == j) {
            return lists[i];
        }

        if (j - i == 1) {
            // 两条链表的合并
            return merge2Lists(lists[i], lists[j]);
        }

        int mid = ((j - i) >> 1) + i;
        ListNode leftList = merge(lists, i, mid);
        ListNode rightList = merge(lists, mid + 1, j);
        // 两条链表的合并
        return merge2Lists(leftList, rightList);
    }

    private ListNode merge2Lists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(), p = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                p.next = l1;
                l1 = l1.next;
            } else {
                p.next = l2;
                l2 = l2.next;
            }
            p = p.next;
        }

        if (l1 == null) {
            p.next = l2;
        }

        if (l2 == null) {
            p.next = l1;
        }

        return dummy.next;
    }
}

1.3 分析这种解法的时空复杂度

1.3.1 时间复杂度

• 图示：4个链表，两两合并的过程。为便于分析，假设每个链表的节点树为a。
  
• i = 1：有$\frac{k}{2}$对合并，每对合并涉及2a个节点。
• i = 2：有$\frac{k}{4}$对合并，每对合并涉及4a个节点。
• 每一层的计算：$\frac{k}{2^i}$ * $2^i\ast a$ = $k\ast a$
• 层数为树高：叶子节点为k（k个链表），树高为logk。
• 因此，时间复杂度为：O(aklogk)。k个链表一共有n个节点，所以，a简化为$\frac{n}{k}$，时间复杂度简化为：O(nlogk)

1.3.2 空间复杂度

• 递归调用，栈深度为树高，因此，空间复杂度为O(logk)

2、优先队列

• 给定一组元素，使得队列的头是最小/大元素。

2.1 PriorityQueue的使用

public class Main {
    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(2);
        ListNode listNode2 = new ListNode(1);
        listNode1.setNext(listNode2);

        // 小根堆
        Queue<ListNode> queue = new PriorityQueue<>(Comparator.comparingInt(ListNode::getVal));
        // 将指定的元素插入到此优先级队列中。（相当于offer()方法）
        queue.add(listNode1);
        queue.add(listNode2);

        while (!queue.isEmpty()) {
            // 检索并删除此队列的头，如果此队列为空，则返回 null 。
            System.out.println(queue.poll());
        }
    }
}

/*
ListNode(val=1, next=null) 
ListNode(val=2, next=ListNode(val=1, next=null))
*/

• 既然要对元素进行排序，要么元素的类实现了Comparable接口（这个要求较高），要么就传入一个自定义的Comparator（这个更灵活）。

2.2 本题代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) {
            return null;
        }

        ListNode dummy = new ListNode(), p = dummy;
        Queue<ListNode> queue = new PriorityQueue<>((node1, node2) -> node1.val - node2.val);
        for (int i = 0; i < lists.length; i++) {
            if (lists[i] != null) {
                ListNode tmp = lists[i];
                while (tmp != null) {
                    queue.add(tmp);
                    tmp = tmp.next;
                }
            }
        }

        while (!queue.isEmpty()) {
            ListNode node = queue.poll();
            p.next = node;
            p = p.next;
        }

        p.next = null; // 合并升序链表问题，别忘了处理尾节点，否则链表可能成环。
        return dummy.next;
    }
}

2.2.1 进一步优化

没必要一次性将所有node都加入优先队列。

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) {
            return null;
        }

        ListNode dummy = new ListNode(), p = dummy;
        Queue<ListNode> queue = new PriorityQueue<>(lists.length, (node1, node2) -> node1.val - node2.val);
        for (ListNode head : lists) {
            if (head != null) {
                queue.offer(head);
            }
        }

        while (!queue.isEmpty()) {
            ListNode node = queue.poll();
            p.next = node;
            p = p.next;

            if (node.next != null) {
                queue.offer(node.next);
            }
        }

        p.next = null;
        return dummy.next;
    }
}

2.3 分析这种解法的时空复杂度

2.3.1 时间复杂度

• 一个k个链表，总共有n个节点。
• 每个节点都会offer和poll优先队列各一次。
• 每次的时间复杂度为O(logk)：队列中最多k个元素，组成的树高为logk。

我们这里用到的优先队列，本质是小根堆，即一种特殊的完全二叉树。一棵由k个元素组成的完全二叉树，其树高为logk。

• 因此，时间复杂度为O(nlogk)

2.3.2 空间复杂度

• 队列中最多k个元素，因此空间复杂度为O(k)