OJ题-合并K个已排序的链表

描述

合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。

数据范围：节点总数 0≤n≤50000≤n≤5000，每个节点的val满足 ∣val∣<=1000∣val∣<=1000

要求：时间复杂度 O(nlogn)O(nlogn)

下面给出C++代码的两种方法：

方法1：使用优先队列（最小堆）

优先队列可以很方便地处理多个链表头节点的最小值，每次从 K 个链表中取出最小的节点，合并到结果链表中。

思路：

使用优先队列（最小堆）来存储每个链表的当前头节点。
每次从堆中取出最小值节点，并将它的下一个节点重新加入堆。

重复这个过程，直到所有链表都被合并。

#include <queue>
#include <vector>
#include <iostream>

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// 比较器，用于优先队列
struct Compare {
    bool operator()(ListNode* a, ListNode* b) {
        return a->val > b->val;
    }
};

class Solution {
public:
    ListNode* mergeKLists(std::vector<ListNode*>& lists) {
        // 使用优先队列（最小堆）
        std::priority_queue<ListNode*, std::vector<ListNode*>, Compare> minHeap;
        
        // 初始化：将每个链表的头节点加入优先队列
        for (auto node : lists) {
            if (node) {
                minHeap.push(node);
            }
        }
        
        // 哑节点，便于构建新链表
        ListNode* dummy = new ListNode(0);
        ListNode* cur = dummy;
        
        // 逐步从最小堆中取出最小的节点，并更新链表
        while (!minHeap.empty()) {
            // 取出最小值节点
            ListNode* minNode = minHeap.top();
            minHeap.pop();
            
            // 将最小节点接到新链表的末尾
            cur->next = minNode;
            cur = cur->next;
            
            // 如果最小节点的下一个节点不为空，将其加入堆中
            if (minNode->next) {
                minHeap.push(minNode->next);
            }
        }
        
        // 返回合并后的链表
        return dummy->next;
    }
};

分析：

1、优先队列的使用：

优先队列使用自定义比较器 Compare，使得最小的节点始终位于堆顶。
每次从堆顶取出最小的节点，并将它的 next 节点放入堆中。

2、时间复杂度：O(N log K)，其中 N 是所有链表节点的总数，K 是链表的个数。每次从优先队列取出最小元素的时间复杂度为 O(log K)，一共需要执行 N 次。

3、空间复杂度：O(K)，优先队列最多存储 K 个元素。

方法2：分治法

可以使用分治法逐步将 K 个链表两两合并，类似于归并排序的过程。每次两两合并直到只剩一个链表。

思路：

将 K 个链表分成两部分，分别合并。
不断递归分治，直到只剩下两个链表，将它们合并。

最终得到合并后的链表。

class Solution {
public:
    // 合并两个有序链表
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (!l1) return l2;
        if (!l2) return l1;
        
        if (l1->val < l2->val) {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        } else {
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
    
    // 分治法合并 K 个链表
    ListNode* mergeKLists(std::vector<ListNode*>& lists) {
        if (lists.empty()) return nullptr;
        return mergeKListsHelper(lists, 0, lists.size() - 1);
    }
    
    // 分治递归函数
    ListNode* mergeKListsHelper(std::vector<ListNode*>& lists, int left, int right) {
        if (left == right) return lists[left];
        int mid = left + (right - left) / 2;
        ListNode* l1 = mergeKListsHelper(lists, left, mid);
        ListNode* l2 = mergeKListsHelper(lists, mid + 1, right);
        return mergeTwoLists(l1, l2);
    }
};