每日算法 — 使用java实现合并K个有序链表：优先队列与分治归并策略

问题描述

给定 k 个升序排列的链表，将它们合并成一个新的升序链表。每个链表内部已排序，链表之间无序。

该问题是大规模数据外部排序的核心子过程，在数据库归并操作、日志文件合并、搜索引擎索引合并等场景中频繁出现。

数据结构定义

public class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }

    // 辅助方法：从数组构建链表
    static ListNode fromArray(int[] arr) {
        if (arr == null || arr.length == 0) return null;
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        for (int v : arr) {
            cur.next = new ListNode(v);
            cur = cur.next;
        }
        return dummy.next;
    }

    // 辅助方法：打印链表
    static void print(ListNode head) {
        while (head != null) {
            System.out.print(head.val + (head.next != null ? " -> " : ""));
            head = head.next;
        }
        System.out.println();
    }
}

解法一：优先队列（最小堆）

维护一个大小为 k 的最小堆，每次取出堆顶最小元素，并将其所在链表的下一个节点入堆。

import java.util.PriorityQueue;
import java.util.Comparator;

public class MergeKListsPQ {

    // O(N log K) 时间，O(K) 额外空间，N为总节点数
    public static ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;

        // 最小堆，按节点值排序
        PriorityQueue<ListNode> pq = new PriorityQueue<>(
            Comparator.comparingInt(a -> a.val)
        );

        // 初始化：每个链表的头节点入堆
        for (ListNode node : lists) {
            if (node != null) pq.offer(node);
        }

        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;

        while (!pq.isEmpty()) {
            ListNode minNode = pq.poll();
            tail.next = minNode;
            tail = tail.next;

            if (minNode.next != null) {
                pq.offer(minNode.next);
            }
        }

        return dummy.next;
    }

    public static void main(String[] args) {
        ListNode[] lists = {
            ListNode.fromArray(new int[]{1, 4, 5}),
            ListNode.fromArray(new int[]{1, 3, 4}),
            ListNode.fromArray(new int[]{2, 6})
        };
        ListNode result = mergeKLists(lists);
        ListNode.print(result); // 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6
    }
}

解法二：分治两两归并

借鉴归并排序思想，将 k 个链表两两配对合并，递归直到只剩一个链表。

public class MergeKListsDivideConquer {

    // O(N log K) 时间，O(log K) 递归栈空间
    public static ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        return mergeRange(lists, 0, lists.length - 1);
    }

    private static ListNode mergeRange(ListNode[] lists, int left, int right) {
        if (left == right) return lists[left];
        int mid = left + (right - left) / 2;
        ListNode l1 = mergeRange(lists, left, mid);
        ListNode l2 = mergeRange(lists, mid + 1, right);
        return mergeTwoLists(l1, l2);
    }

    // 合并两个有序链表 O(n)
    private static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;

        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }

        cur.next = (l1 != null) ? l1 : l2;
        return dummy.next;
    }

    public static void main(String[] args) {
        ListNode[] lists = {
            ListNode.fromArray(new int[]{1, 4, 5}),
            ListNode.fromArray(new int[]{1, 3, 4}),
            ListNode.fromArray(new int[]{2, 6})
        };
        ListNode result = mergeKLists(lists);
        ListNode.print(result);
    }
}

解法三：顺序归并（暴力）

public class MergeKListsSequential {

    // O(N * K) 时间，O(1) 额外空间
    public static ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        ListNode result = lists[0];
        for (int i = 1; i < lists.length; i++) {
            result = mergeTwoLists(result, lists[i]);
        }
        return result;
    }

    private static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                cur.next = l1; l1 = l1.next;
            } else {
                cur.next = l2; l2 = l2.next;
            }
            cur = cur.next;
        }
        cur.next = (l1 != null) ? l1 : l2;
        return dummy.next;
    }
}

复杂度对比

实际应用

在数据库外部排序中，当内存无法容纳全部数据时，会将数据分块排序后产生多个有序”顺串”（run），再用多路归并合并为最终有序结果。合并 K 个有序链表正是这一过程的核心算法。

总结

本文从暴力顺序归并出发，逐步优化到优先队列与分治策略，展示了算法设计中”减少比较次数”与”降低空间开销”的双重优化目标。读者可进一步思考：若要求合并后的链表去重，应如何修改？