Hard

题目描述

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到：
1->1->2->3->4->4->5->6

示例 2：

输入：lists = []
输出：[]

示例 3：

输入：lists = [[]]
输出：[]

提示：

  • k == lists.length
  • 0 <= k <= 10^4
  • 0 <= lists[i].length <= 500
  • -10^4 <= lists[i][j] <= 10^4
  • lists[i] 按升序排列
  • lists[i].length 的总和不会超过 10^4

解题思路

这是一个经典的分治问题，有三种主要解法：

方法一：逐一合并（暴力法）
依次将每个链表与结果链表合并，时间复杂度较高。

方法二：分治合并（推荐）
采用分治思想，将k个链表两两配对进行合并，类似归并排序的思路。每轮合并后链表数量减半，直到只剩一个链表。这种方法效率最高，是最优解。

方法三：优先队列（堆）
使用最小堆维护每个链表的当前节点，每次取出最小值节点，然后将该节点的下一个节点加入堆中。

分治法是最优解法，其核心思想是：先将相邻的链表两两合并，得到k/2个链表；然后继续两两合并，直到最终合并成一个链表。这样可以最大化利用已有的有序性，避免重复比较。

具体实现中，我们需要实现一个合并两个有序链表的辅助函数，然后在主函数中递归调用分治逻辑。

代码实现

class Solution {
private:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode dummy(0);
        ListNode* curr = &dummy;
        
        while (l1 && l2) {
            if (l1->val <= l2->val) {
                curr->next = l1;
                l1 = l1->next;
            } else {
                curr->next = l2;
                l2 = l2->next;
            }
            curr = curr->next;
        }
        
        curr->next = l1 ? l1 : l2;
        return dummy.next;
    }
    
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty()) return nullptr;
        
        while (lists.size() > 1) {
            vector<ListNode*> mergedLists;
            
            for (int i = 0; i < lists.size(); i += 2) {
                ListNode* l1 = lists[i];
                ListNode* l2 = (i + 1 < lists.size()) ? lists[i + 1] : nullptr;
                mergedLists.push_back(mergeTwoLists(l1, l2));
            }
            
            lists = mergedLists;
        }
        
        return lists[0];
    }
};

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        if not lists:
            return None
        
        def mergeTwoLists(l1, l2):
            dummy = ListNode(0)
            curr = dummy
            
            while l1 and l2:
                if l1.val <= l2.val:
                    curr.next = l1
                    l1 = l1.next
                else:
                    curr.next = l2
                    l2 = l2.next
                curr = curr.next
            
            curr.next = l1 or l2
            return dummy.next
        
        while len(lists) > 1:
            merged_lists = []
            
            for i in range(0, len(lists), 2):
                l1 = lists[i]
                l2 = lists[i + 1] if i + 1 < len(lists) else None
                merged_lists.append(mergeTwoLists(l1, l2))
            
            lists = merged_lists
        
        return lists[0]

public class Solution {
    private ListNode MergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                curr.next = l1;
                l1 = l1.next;
            } else {
                curr.next = l2;
                l2 = l2.next;
            }
            curr = curr.next;
        }
        
        curr.next = l1 ?? l2;
        return dummy.next;
    }
    
    public ListNode MergeKLists(ListNode[] lists) {
        if (lists.Length == 0) return null;
        
        List<ListNode> listsList = new List<ListNode>(lists);
        
        while (listsList.Count > 1) {
            List<ListNode> mergedLists = new List<ListNode>();
            
            for (int i = 0; i < listsList.Count; i += 2) {
                ListNode l1 = listsList[i];
                ListNode l2 = (i + 1 < listsList.Count) ? listsList[i + 1] : null;
                mergedLists.Add(MergeTwoLists(l1, l2));
            }
            
            listsList = mergedLists;
        }
        
        return listsList[0];
    }
}

var mergeKLists = function(lists) {
    if (!lists || lists.length === 0) return null;
    
    while (lists.length > 1) {
        let mergedLists = [];
        
        for (let i = 0; i < lists.length; i += 2) {
            let l1 = lists[i];
            let l2 = (i + 1 < lists.length) ? lists[i + 1] : null;
            mergedLists.push(mergeTwoLists(l1, l2));
        }
        
        lists = mergedLists;
    }
    
    return lists[0];
};

function mergeTwoLists(l1, l2) {
    let dummy = new ListNode();
    let current = dummy;
    
    while (l1 && l2) {
        if (l1.val <= l2.val) {
            current.next = l1;
            l1 = l1.next;
        } else {
            current.next = l2;
            l2 = l2.next;
        }
        current = current.next;
    }
    
    current.next = l1 || l2;
    
    return dummy.next;
}
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分治法
时间复杂度O(N log k)，其中N是所有节点总数，k是链表数量
空间复杂度O(1)，只使用常数额外空间（不考虑递归栈空间）

相关题目