{"id":925,"date":"2025-12-11T19:01:00","date_gmt":"2025-12-11T11:01:00","guid":{"rendered":"https:\/\/www.guanhaobo.cn\/?p=925"},"modified":"2025-12-11T19:01:00","modified_gmt":"2025-12-11T11:01:00","slug":"leetcode-23-%e5%90%88%e5%b9%b6-k-%e4%b8%aa%e5%8d%87%e5%ba%8f%e9%93%be%e8%a1%a8","status":"publish","type":"post","link":"https:\/\/www.guanhaobo.cn\/?p=925","title":{"rendered":"LeetCode 23 \u2014 \u5408\u5e76 K \u4e2a\u5347\u5e8f\u94fe\u8868"},"content":{"rendered":"

\u9898\u76ee\u63cf\u8ff0<\/h1>\n

\u7ed9\u4f60\u4e00\u4e2a\u94fe\u8868\u6570\u7ec4\uff0c\u6bcf\u4e2a\u94fe\u8868\u90fd\u5df2\u7ecf\u6309\u5347\u5e8f\u6392\u5217\u3002
\n\u8bf7\u4f60\u5c06\u6240\u6709\u94fe\u8868\u5408\u5e76\u5230\u4e00\u4e2a\u5347\u5e8f\u94fe\u8868\u4e2d\uff0c\u8fd4\u56de\u5408\u5e76\u540e\u7684\u94fe\u8868\u3002<\/p>\n

\u8f93\u5165\uff1alists = [[1,4,5],[1,3,4],[2,6]]
\n\u8f93\u51fa\uff1a[1,1,2,3,4,4,5,6]
\n\u89e3\u91ca\uff1a\u94fe\u8868\u6570\u7ec4\u5982\u4e0b\uff1a
\n[
\n 1->4->5,
\n 1->3->4,
\n 2->6
\n]
\n\u5c06\u5b83\u4eec\u5408\u5e76\u5230\u4e00\u4e2a\u6709\u5e8f\u94fe\u8868\u4e2d\u5f97\u5230\u3002
\n1->1->2->3->4->4->5->6<\/p>\n

\u9898\u76ee\u5206\u6790<\/h1>\n

\u5047\u8bbe\u94fe\u8868\u6570\u91cf\u4e3a k\uff0c\u6240\u6709\u94fe\u8868\u8282\u70b9\u603b\u6570\u4e3a n
\n\u4f7f\u7528\u4f18\u5148\u961f\u5217\u6765\u5bfb\u627e\u6700\u5c0f\u503c
\n1. \u628a k \u4e2a\u5934\u8282\u70b9\u653e\u5165\u961f\u5217\u4e2d
\n2. \u4ece\u961f\u5217\u4e2d\u53d6\u51fa\u6700\u5c0f\u503c\uff0c\u540c\u65f6\u628a\u5b83\u7684next\u653e\u8fdb\u961f\u5217<\/p>\n

\u961f\u5217\u5185\u6700\u591a\u540c\u65f6\u5b58\u5728 k \u4e2a\u5143\u7d20\uff0c\u56e0\u6b64\u6bcf\u6b21\u53d6\u6700\u5c0f\u503c\uff0c\u65f6\u95f4\u590d\u6742\u5ea6\u90fd\u662f O(log k)
\n\u4e00\u5171\u9700\u8981\u53d6\u503c n \u6b21\uff0c\u65f6\u95f4\u590d\u6742\u5ea6\u662f O(n * log k)<\/p>\n

Java<\/h1>\n
public ListNode mergeKLists(ListNode[] lists) {\n    ListNode ans = new ListNode();\n    ListNode cur = ans;\n    PriorityQueue<ListNode> queue = new PriorityQueue<>((o1, o2) -> Integer.compare(o1.val, o2.val));\n    for (ListNode node : lists) {\n        if (node != null) {\n            queue.offer(node);\n        }\n    }\n    while (!queue.isEmpty()) {\n        ListNode node = queue.poll();\n        if (node.next != null) {\n            queue.offer(node.next);\n        }\n        cur.next = node;\n        cur = cur.next;\n    }\n\n    return ans.next;\n}\n<\/code><\/pre>\n
Kotlin<\/h1>\n
fun mergeKLists(lists: Array<ListNode?>): ListNode? {\n    val ans = ListNode(0)\n    var cur = ans\n    val queue = PriorityQueue<ListNode> { o1, o2 -> Integer.compare(o1.`val`, o2.`val`) }\n    for (node in lists) {\n        if (node != null) {\n            queue.offer(node)\n        }\n    }\n    while (!queue.isEmpty()) {\n        val node = queue.poll()\n        if (node.next != null) {\n            queue.offer(node.next)\n        }\n        cur.next = node\n        cur = cur.next\n    }\n    return ans.next\n}\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
\u9898\u76ee\u63cf\u8ff0 \u7ed9\u4f60\u4e00\u4e2a\u94fe\u8868\u6570\u7ec4\uff0c\u6bcf\u4e2a\u94fe\u8868\u90fd\u5df2\u7ecf\u6309\u5347\u5e8f\u6392\u5217\u3002 \u8bf7\u4f60\u5c06\u6240\u6709\u94fe\u8868\u5408\u5e76\u5230\u4e00\u4e2a\u5347\u5e8f\u94fe\u8868\u4e2d\uff0c\u8fd4\u56de\u5408\u5e76\u540e\u7684\u94fe\u8868\u3002 […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[5],"tags":[20,79,51,84],"class_list":["post-925","post","type-post","status-publish","format-standard","hentry","category-algo","tag-leetcode","tag-79","tag-51","tag-84"],"_links":{"self":[{"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/posts\/925","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=925"}],"version-history":[{"count":1,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/posts\/925\/revisions"}],"predecessor-version":[{"id":926,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/posts\/925\/revisions\/926"}],"wp:attachment":[{"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=925"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=925"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=925"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}