合并 k 个升序链表

题解思路

本题要求将多个已排序的链表合并成一个升序的链表。每个链表中的元素都已经排好序，我们需要利用这些已排序链表的信息将其合并为一个新的有序链表。

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

最小堆是一种数据结构，它支持在对元素进行插入和删除时，始终保持堆顶元素为最小值。我们可以利用最小堆来实现这个问题。

思路：

1. 初始化最小堆：首先，我们将所有链表的头节点放入最小堆中。堆中的元素会按节点的值排序。这样，堆顶元素就是当前最小的节点。

2. 逐步合并：每次从最小堆中弹出一个节点，将它加入到结果链表中，然后将弹出节点的下一个节点（如果存在）加入堆中。这样，堆中始终保持着当前最小的节点，直到所有链表都被合并完。

3. 时间复杂度分析：插入堆和删除堆顶元素的时间复杂度是 O(log k)，其中 k 是链表的数量。每个节点最多会被操作一次，假设总节点数为 n，则总体时间复杂度为 O(n log k)。

方法二：两两合并

我们还可以采用两两合并的方法来解题。首先将两个链表合并成一个有序链表，然后再将结果与下一个链表合并，直到所有链表合并完。

思路：

1. 两两合并：首先选择两个链表进行合并，得到一个有序链表。然后将该链表与下一个链表合并，再得到一个新的有序链表。重复这一过程，直到所有链表都合并到一起。

2. 时间复杂度分析：每次合并两个链表的时间复杂度是 O(n)，其中 n 是链表中的节点数。由于最多需要合并 k 次，整体的时间复杂度为 O(k * n)。

Python 代码实现(方法一)

import heapq

# 定义链表节点类
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# 合并 k 个升序链表
def mergeKLists(lists):
    # 创建一个最小堆
    heap = []
    
    # 将所有链表的头节点入堆
    for i in range(len(lists)):
        if lists[i]:
            heapq.heappush(heap, (lists[i].val, i, lists[i]))
    
    # 创建一个虚拟头节点，方便操作
    dummy = ListNode()
    current = dummy
    
    # 逐个弹出堆中的节点并加入结果链表
    while heap:
        val, idx, node = heapq.heappop(heap)
        current.next = node
        current = current.next
        if node.next:
            heapq.heappush(heap, (node.next.val, idx, node.next))
    
    return dummy.next

# 生成链表的方法（根据输入数据生成链表）
def generate_linked_list(nums):
    dummy = ListNode()
    current = dummy
    for num in nums:
        current.next = ListNode(num)
        current = current.next
    return dummy.next

# 读取输入并进行合并
k = int(input())  # 输入链表的数量
lists = []
for _ in range(k):
    nums = list(map(int, input().split()))  # 读取每个链表
    lists.append(generate_linked_list(nums))

# 合并链表
result = mergeKLists(lists)

# 输出合并后的链表
output = []
while result:
    output.append(str(result.val))
    result = result.next
print(" ".join(output))

Java 代码实现(方法一)

import java.io.*;
import java.util.*;

// 定义链表节点类
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 Main {
    
    // 合并 k 个有序链表
    public static ListNode mergeKLists(ListNode[] lists) {
        // 使用优先队列，按节点值升序排序
        PriorityQueue<ListNode> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a.val));
        
        // 将每个链表的头节点（非空）加入队列
        for (ListNode list : lists) {
            if (list != null) {
                pq.offer(list);
            }
        }
        
        // 创建虚拟头节点，便于构造结果链表
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        
        // 弹出队列中的最小节点，若该节点有后继，则将后继加入队列
        while (!pq.isEmpty()) {
            ListNode node = pq.poll();
            current.next = node;
            current = current.next;
            if (node.next != null) {
                pq.offer(node.next);
            }
        }
        
        return dummy.next;
    }

    public static void main(String[] args) throws IOException {
        // 使用 BufferedReader 按行读取输入
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine();
        if(line == null || line.trim().isEmpty()){
            return;
        }
        int k = Integer.parseInt(line.trim());
        ListNode[] lists = new ListNode[k];
        
        for (int i = 0; i < k; i++) {
            String str = br.readLine();
            if(str == null || str.trim().isEmpty()){
                lists[i] = null;
                continue;
            }
            // 分割当前行中的所有整数
            String[] tokens = str.trim().split("\\s+");
            ListNode dummy = new ListNode(0);
            ListNode current = dummy;
            for (String token : tokens) {
                int val = Integer.parseInt(token);
                current.next = new ListNode(val);
                current = current.next;
            }
            lists[i] = dummy.next;
        }
        
        // 调用合并链表函数
        ListNode result = mergeKLists(lists);
        
        // 输出合并后的链表节点值，用空格隔开
        StringBuilder sb = new StringBuilder();
        while (result != null) {
            sb.append(result.val).append(" ");
            result = result.next;
        }
        System.out.println(sb.toString().trim());
    }
}

C++ 代码实现(方法一)

#include <iostream>
#include <sstream>
#include <vector>
#include <queue>
#include <string>
using namespace std;

// 定义链表节点结构体
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// 比较器，用于优先队列（小顶堆）
struct cmp {
    bool operator()(ListNode* a, ListNode* b) {
        return a->val > b->val; // 值越小优先级越高
    }
};

// 合并 k 个有序链表
ListNode* mergeKLists(vector<ListNode*>& lists) {
    priority_queue<ListNode*, vector<ListNode*>, cmp> pq;
    
    // 将每个链表的头节点（非空）入堆
    for (auto node : lists) {
        if (node)
            pq.push(node);
    }
    
    ListNode* dummy = new ListNode(0);
    ListNode* current = dummy;
    
    while (!pq.empty()) {
        ListNode* node = pq.top();
        pq.pop();
        current->next = node;
        current = current->next;
        if (node->next)
            pq.push(node->next);
    }
    
    ListNode* head = dummy->next;
    delete dummy;
    return head;
}

int main() {
    int k;
    string line;
    
    // 读取第一行 k 的值
    getline(cin, line);
    k = stoi(line);
    vector<ListNode*> lists;
    
    // 逐行读取每个链表的数据
    for (int i = 0; i < k; i++) {
        getline(cin, line);
        if(line.empty()){
            lists.push_back(nullptr);
            continue;
        }
        istringstream iss(line);
        int val;
        ListNode* dummy = new ListNode(0);
        ListNode* current = dummy;
        // 读取当前行的所有整数
        while (iss >> val) {
            current->next = new ListNode(val);
            current = current->next;
        }
        lists.push_back(dummy->next);
        delete dummy;
    }
    
    // 合并链表
    ListNode* merged = mergeKLists(lists);
    
    // 输出结果
    while (merged) {
        cout << merged->val;
        merged = merged->next;
        if(merged) cout << " ";
    }
    cout << endl;
    
    return 0;
}

Leetcode 34.合并K个升序链表-原题链接

题目内容

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

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

输入描述

第一行为一个整数$k$， 接下来的$k$行，每行若干个整数，以空格隔开，表示一个链表节点的值。

输出描述

输出共一行，包含排序后链表节点的值，用空格隔开。

样例1

输入

3
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$

提示

• $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$