leetcode
leetcode 3001 ~ 3050
合并 K 个升序链表

合并 K 个升序链表

难度:

标签:

题目描述

English description is not available for the problem. Please switch to Chinese.

代码结果

运行时间: 52 ms, 内存: 18.6 MB

/*
 思路：
 使用流式处理方法，将所有链表节点收集到一个列表中，然后排序，最后重新构建链表。
*/
import java.util.*;
import java.util.stream.*;

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class MergeKSortedListsStream {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        List<ListNode> nodeList = Arrays.stream(lists)
                                         .filter(Objects::nonNull)
                                         .flatMap(list -> {
                                             List<ListNode> nodes = new ArrayList<>();
                                             while (list != null) {
                                                 nodes.add(list);
                                                 list = list.next;
                                             }
                                             return nodes.stream();
                                         })
                                         .sorted(Comparator.comparingInt(n -> n.val))
                                         .collect(Collectors.toList());
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        for (ListNode node : nodeList) {
            current.next = node;
            current = current.next;
        }
        current.next = null;
        return dummy.next;
    }
}

解释

方法:

这个题解采用了分治法的思想，将合并 k 个链表的问题分解为合并两个链表的问题。具体做法是： 1. 如果链表数组长度为 1，直接返回该链表。 2. 如果链表数组长度大于 1，将其分为两半，分别对这两半递归地进行合并。 3. 合并两个链表的过程中，使用一个虚拟头节点，依次比较两个链表的节点值，将较小的节点接到结果链表上，直到其中一个链表为空，再将另一个链表剩余部分接到结果链表上。

时间复杂度:

O(kn * log(k))

空间复杂度:

O(log(k))

代码细节讲解

🦆
在实现分治法合并链表的过程中，为什么选择递归而不是迭代？递归方法是否对内存和性能有特定的影响？
▷
在合并 k 个链表时，递归方法能够将问题自然地分解为更小的子问题，这与分治法的核心思想相吻合。使用递归，代码更为简洁且易于理解。相较于迭代，递归可能在内存使用上稍高，因为每次递归调用都会占用一定的调用栈空间。在极端情况下，如递归深度过大，可能导致栈溢出。性能方面，递归与迭代相比通常有更多的函数调用开销，但在合并链表这个问题上，递归的时间复杂度与迭代相当，都可以达到 O(Nlogk)，其中 N 是所有链表中节点总数，k 是链表数目。
🦆
对于输入链表数组为空（`lists = []`）或全部链表为空（`lists = [[]]`）的情况，解决方案是否有特殊处理？如果没有，如何改进代码以更优雅地处理这些边界情况？
▷
当前的解决方案没有特别处理`lists = []`或`lists = [[]]`的情况。对于`lists = []`，函数会在`merge_list(0, -1)`时返回`None`，这是正确的。但是，为了让代码更加健壮和直观，可以在`mergeKLists`函数的开始添加检查条件：`if not lists: return None`。这样可以明确表示当输入为空时，输出也应该为空。此外，对于`lists`中每个元素都是空链表的情况，我们可以在递归函数`merge_list`中进行处理，确保返回一个空链表而非`None`。
🦆
递归函数`merge_list`在处理`l > r`的情况时直接返回`None`，这是否会影响合并的最终结果，尤其是在某些子数组为空的情况下？
▷
在`merge_list`函数中，当`l > r`时返回`None`是处理边界情况的一种方式，确保不会有非法的数组访问。这通常不会影响最终结果，因为这种情况发生在递归分解到不存在的子区间时。在实际合并过程中，如果某一部分的递归返回`None`（表示这部分没有链表存在），合并函数`merge`能够处理一个或两个链表为`None`的情况。确保即使是空链表也能正确合并，不会对最终结果产生负面影响。

相关问题

排序链表子集