合并 K 个排序链表

2025年3月17日 | 阅读 8 分钟

问题陈述

在此陈述中，我们有一个链表列表，其中每个链表都按升序排序。您需要以非降序（升序）合并这些链表，从而获得一个有序列表。

样本测试用例

Test Case 1 : 
Input: K = 2, N = 3
list1 = 1->4->7->NULL
list2 = 2->5->8->NULL
Output: 1->2->4->5->7->8

Test Case 2:
Input: K = 3, N = 3
list1 = 2->5->8->NULL
list2 = 1->4->7->NULL
list3 = 3->6->9->NULL
Output: 1->2->3->4->5->6->7->8->9

注意：在阅读本文之前，请尝试先想出一种方法，以便更好地理解。

方法 1：暴力枚举法

一种直接的方法是使用第一个列表初始化结果，然后遍历其余列表。对于当前列表中的每个节点，以排序方式将其插入到结果中。

以下是上述方法的 Java 实现

public class MergeKSortedLists { // 链表节点类 static class ListNode { int data; ListNode next; public ListNode(int data) { this.data = data; this.next = null; } } static void printList(ListNode node) { while (node != null) { System.out.print(node.data + " "); node = node.next; } } // 主函数，接受一个链表数组并生成排序后的输出 static ListNode mergeKLists(ListNode[] lists, int last) { for (int i = 1; i <= last; i++) { while (true) { ListNode head0 = lists[0], headI = lists[i]; if (headI == null) break; if (head0.data >= headI.data) { lists[i] = headI.next; headI.next = head0; lists[0] = headI; } else { while (head0.next != null) { if (head0.next.data >= headI.data) { lists[i] = headI.next; headI.next = head0.next; head0.next = headI; break; } head0 = head0.next; if (head0.next == null) { lists[i] = headI.next; headI.next = null; head0.next = headI; head0.next.next = null; break; } } } } } return lists[0]; } // 用于创建新节点的实用函数 static ListNode newNode(int data) { return new ListNode(data); } // 驱动程序以测试上述函数 public static void main(String[] args) { // 链表数量 int k = 3; // 每个列表中的元素数量 int n = 4; // 存储链表头节点的指针数组 ListNode[] lists = new ListNode[k]; lists[0] = newNode(1); lists[0].next = newNode(3); lists[0].next.next = newNode(5); lists[0].next.next.next = newNode(7); lists[1] = newNode(2); lists[1].next = newNode(4); lists[1].next.next = newNode(6); lists[1].next.next.next = newNode(8); lists[2] = newNode(0); lists[2].next = newNode(9); lists[2].next.next = newNode(10); lists[2].next.next.next = newNode(11); // 合并所有列表 ListNode head = mergeKLists(lists, k - 1); // 打印合并后的列表 printList(head); } }

public class MergeKSortedLists {
    // Node class for linked list
    static class ListNode {
        int data;
        ListNode next;
        public ListNode(int data) {
            this.data = data;
            this.next = null;
        }
    }

    static void printList(ListNode node) {
        while (node != null) {
            System.out.print(node.data + " ");
            node = node.next;
        }
    }
    // Main function that takes an array of lists and generates the sorted output
    static ListNode mergeKLists(ListNode[] lists, int last) {
        for (int i = 1; i <= last; i++) {
            while (true) {
                ListNode head0 = lists[0], headI = lists[i];
                if (headI == null)
                    break;
                if (head0.data >= headI.data) {
                    lists[i] = headI.next;
                    headI.next = head0;
                    lists[0] = headI;
                } else {
                    while (head0.next != null) {
                        if (head0.next.data >= headI.data) {
                            lists[i] = headI.next;
                            headI.next = head0.next;
                            head0.next = headI;
                            break;
                        }
            head0 = head0.next;
                        if (head0.next == null) {
                            lists[i] = headI.next;
                            headI.next = null;
                            head0.next = headI;
                            head0.next.next = null;
                            break;
                        }
                    }
                }
            }
        }
        return lists[0];
    }
    // Utility function to create a new node
    static ListNode newNode(int data) {
        return new ListNode(data);
    }
    // Driver program to test above functions
    public static void main(String[] args) {
        // Number of linked lists
        int k = 3;
        // Number of elements in each list
        int n = 4;
        // Array of pointers storing the head nodes of the linked lists
        ListNode[] lists = new ListNode[k];
        lists[0] = newNode(1);
        lists[0].next = newNode(3);
        lists[0].next.next = newNode(5);
        lists[0].next.next.next = newNode(7);
        lists[1] = newNode(2);
        lists[1].next = newNode(4);
        lists[1].next.next = newNode(6);
        lists[1].next.next.next = newNode(8);

        lists[2] = newNode(0);
        lists[2].next = newNode(9);
        lists[2].next.next = newNode(10);
        lists[2].next.next.next = newNode(11);
        // Merge all lists
        ListNode head = mergeKLists(lists, k - 1);
        // Print the merged list
        printList(head);
    }
}

输出

复杂度分析

时间复杂度： O(n^k-1)，因为我们对每个 K 列表都遍历了 n 次。

空间复杂度： O(1)。

方法 2：使用最小堆

此解决方案采用最小堆方法。最初，通过从每个 K 个链表中插入第一个元素来构建一个最小堆。该算法通过从最小堆中提取根元素并将其附加到输出链表来继续。随后，将与提取的元素关联的链表中的下一个元素插入到最小堆中。此过程重复进行，直到最小堆中没有剩余元素，最终产生所需的结果。

算法

创建一个最小堆来存储来自 K 个链表的元素及其列表索引。
将每个链表的第一个元素及其列表索引插入到最小堆中。
初始化一个空的链表结果。
重复以下步骤，直到最小堆不为空
- 从最小堆中提取根元素，其中包含最小值及其列表索引。
- 将提取的元素附加到结果链表。
- 如果与提取的元素关联的链表中存在下一个元素，则将该元素及其列表索引插入到最小堆中。
返回结果链表的头节点。

注意：最小堆确保在剩余的候选元素中最小的元素始终位于根部，从而有助于构建排序后的合并列表。当最小堆中没有更多元素时，算法终止，表示所有链表都已处理。

上述方法的 Java 实现

import java.util.PriorityQueue;
class ListNode {
    int data;
    ListNode next;
    public ListNode(int data) {
        this.data = data;
        this.next = null;
    }
}
class NodeComparator implements Comparable<ListNode> {
    public int compare(ListNode a, ListNode b) {
        return a.data - b.data;
    }
}
public class MergeKSortedLists {
    public static ListNode mergeKSortedLists(ListNode[] lists, int k) {
        PriorityQueue<ListNode> minHeap = new PriorityQueue<>(new NodeComparator());
        // Push the head nodes of all the k lists into the minHeap
        for (int i = 0; i < k; i++) {
            if (lists[i] != null) {
                minHeap.add(lists[i]);
            }
        }
        // Handles the case when k = 0 or lists have no elements in them
        if (minHeap.isEmpty()) {
            return null;
        }
        ListNode dummy = new ListNode(0);
        ListNode last = dummy;
        // Loop until minHeap is not empty
        while (!minHeap.isEmpty()) {
            // Get the top element of minHeap
            ListNode current = minHeap.poll();
            // Add the top element of minHeap to the resultant merged list
            last.next = current;
            last = last.next;
            // Check if there is a node next to the 'top' node
            // in the list of which the 'top' node is a member
            if (current.next != null) {
                // Push the next node of the top node in minHeap
                minHeap.add(current.next);
            }
        }
        // Address of the head node of the required merged list
        return dummy.next;
    }
    public static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.data + " ");
            head = head.next;
        }
    }
    public static void main(String[] args) {
        // Number of linked lists
        int numLists = 3;
        // Number of elements in each list
        int numElements = 4;
        // Array of pointers storing the head nodes of the linked lists
        ListNode[] lists = new ListNode[numLists];
        // Creating k = 3 sorted lists
        lists[0] = new ListNode(1);
        lists[0].next = new ListNode(3);
        lists[0].next.next = new ListNode(5);
        lists[0].next.next.next = new ListNode(7);
        lists[1] = new ListNode(2);
        lists[1].next = new ListNode(4);
        lists[1].next.next = new ListNode(6);
        lists[1].next.next.next = new ListNode(8);
        lists[2] = new ListNode(0);
        lists[2].next = new ListNode(9);
        lists[2].next.next = new ListNode(10);
        lists[2].next.next.next = new ListNode(11);

        // Merge the k sorted lists
        ListNode head = mergeKSortedLists(lists, numLists);
        // Print the merged list
        printList(head);
    }
}

说明

输出

复杂度分析

时间复杂度：O(n*k*logk)

空间复杂度：O(k)

方法 3：使用分治法

该方法涉及迭代地配对排序列表，在每次迭代中将列表总数减半，直到所有列表合并。

按照以下步骤解决问题

通过以线性时间复杂度高效地合并每对列表，并利用 O(N) 空间来合并 K 个列表。
在初始循环之后，将有 K/2 个列表，每个列表的大小为 2N。随后，在第二个循环中，将有 K/4 个列表，每个列表的大小为 4N，依此类推。
迭代地继续此过程，直到只剩下一个列表。

上述方法的 Java 实现

public class MergeKSortedLists {
    // Node class for linked list
    static class ListNode {
        int data;
        ListNode next;
        public ListNode(int data) {
            this.data = data;
            this.next = null;
        }
    }
    static void printList(ListNode node) {
        while (node != null) {
            System.out.print(node.data + " ");
            node = node.next;
        }
    }

    // Takes two lists sorted in increasing order and merges their nodes together to create a single sorted list.
    // This function uses O(n) extra space for recursive calls.
    static ListNode sortedMerge(ListNode a, ListNode b) {
        ListNode result = null;
        // Base cases
        if (a == null)
            return b;
        else if (b == null)
            return a;
        // Pick either a or b, and recur
        if (a.data <= b.data) {
            result = a;
            result.next = sortedMerge(a.next, b);
        } else {
            result = b;
            result.next = sortedMerge(a, b.next);
        }
        return result;
    }
    // The main function that takes an array of lists arr[0..last] and generates the sorted output
    static ListNode mergeKLists(ListNode[] arr, int last) {
        // Repeat until only one list is left
        while (last != 0) {
           int i = 0, j = last;
            // (i, j) forms a pair
            while (i < j) {
                // Merge List i with List j and store the merged list in List i
                arr[i] = sortedMerge(arr[i], arr[j]);
                // Consider the next pair
                i++;
                j--;
                // If all pairs are merged, update last
                if (i >= j)
                    last = j;
            }
        }
        return arr[0];
    }

    // Utility function to create a new node
    static ListNode newNode(int data) {
        ListNode temp = new ListNode(data);
        temp.next = null;
        return temp;
    }
    public static void main(String[] args) {
        int k = 3; // Number of linked lists
        int n = 4; // Number of elements in each list
        // An array of pointers storing the head nodes of the linked lists
        ListNode[] lists = new ListNode[k];
        // Creating k = 3 sorted lists
        lists[0] = newNode(1);
        lists[0].next = newNode(3);
        lists[0].next.next = newNode(5);
        lists[0].next.next.next = newNode(7);
        lists[1] = newNode(2);
        lists[1].next = newNode(4);
        lists[1].next.next = newNode(6);
        lists[1].next.next.next = newNode(8);
        lists[2] = newNode(0);
        lists[2].next = newNode(9);
        lists[2].next.next = newNode(10);
        lists[2].next.next.next = newNode(11);
        // Merge all lists
        ListNode head = mergeKLists(lists, k - 1);
        // Print the merged list
        printList(head);
    }
}

输出

复杂度分析

时间复杂度：O(n*k^2)

空间复杂度：O(n)

下一个主题最接近给定数字的三元组和

← prev next →

合并 K 个排序链表

注意：在阅读本文之前，请尝试先想出一种方法，以便更好地理解。

注意：最小堆确保在剩余的候选元素中最小的元素始终位于根部，从而有助于构建排序后的合并列表。当最小堆中没有更多元素时，算法终止，表示所有链表都已处理。

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

数据结构教程

DS 数组

DS 链表

DS 栈

DS 队列

DS 树

DS 图

DS 搜索

DS 排序

哈希与堆

差异

二叉树

二叉搜索树

AVL 树

单向链表

双向链表

循环链表

循环双向链表

DS 选择题

其他

合并 K 个排序链表

注意：在阅读本文之前，请尝试先想出一种方法，以便更好地理解。

注意：最小堆确保在剩余的候选元素中最小的元素始终位于根部，从而有助于构建排序后的合并列表。当最小堆中没有更多元素时，算法终止，表示所有链表都已处理。

相关帖子

最优二叉搜索树

排序大整数

双指针技术

就地将 BST 转换为最小堆

数据结构中图的树边和回边区别

Prim 算法和 Kruskal 算法的区别

使用 Trie 实现自动完成功能

二叉树枚举

数据结构中的最优二叉搜索树

约瑟夫环问题使用循环链表

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器