{"id":7401,"date":"2026-07-21T21:48:59","date_gmt":"2026-07-21T13:48:59","guid":{"rendered":"https:\/\/i007.cc\/wordpress\/?p=7401"},"modified":"2026-07-21T21:48:59","modified_gmt":"2026-07-21T13:48:59","slug":"%e5%90%88%e5%b9%b6-k-%e4%b8%aa%e6%9c%89%e5%ba%8f%e9%93%be%e8%a1%a8%ef%bc%88merge-k-sorted-lists%ef%bc%89","status":"publish","type":"post","link":"https:\/\/i007.cc\/wordpress\/archives\/7401","title":{"rendered":"\u5408\u5e76 K \u4e2a\u6709\u5e8f\u94fe\u8868\uff08Merge K Sorted Lists\uff09"},"content":{"rendered":"

\u529b\u6263\u7b2c 23 \u9898\u3002\u7ed9 K \u6761\u6709\u5e8f\u94fe\u8868\uff0c\u5408\u5e76\u6210\u4e00\u6761\u6709\u5e8f\u94fe\u8868\u3002<\/p>\n

\n

\u5148\u4ece\u6700\u7b80\u5355\u7684\u60c5\u51b5\u5efa\u7acb\u76f4\u89c9<\/h4>\n

\u5408\u5e76 2 \u6761<\/strong>\uff08\u529b\u6263 21 \u9898\uff09\u662f\u57fa\u7840\uff0c\u53cc\u6307\u9488\u4e00\u904d\u626b\uff1a<\/p>\n

\n
\n
<\/div>\n<\/div>\n
cpp<\/div>\n
\n
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {\r\n    ListNode dummy(0);\r\n    ListNode* tail = &dummy;\r\n    while (l1 && l2) {\r\n        if (l1->val <= l2->val) { tail->next = l1; l1 = l1->next; }\r\n        else                    { tail->next = l2; l2 = l2->next; }\r\n        tail = tail->next;\r\n    }\r\n    tail->next = l1 ? l1 : l2;\r\n    return dummy.next;\r\n}<\/pre>\n
 <\/p>\n<\/div>\n<\/div>\n
K \u6761\u7684\u95ee\u9898\u5c31\u662f\u5982\u4f55\u9ad8\u6548\u6269\u5c55\u8fd9\u4e2a\u601d\u8def\u3002<\/p>\n
\n
\u89e3\u6cd5\u4e00\uff1a\u6700\u5c0f\u5806\uff08\u4f18\u5148\u961f\u5217\uff09\u2b50 \u6700\u76f4\u89c2<\/h4>\n
\u6bcf\u6b21\u4ece K \u4e2a\u94fe\u8868\u7684\u5f53\u524d\u5934\u8282\u70b9<\/strong>\u4e2d\u53d6\u6700\u5c0f\u503c\uff0c\u7528\u5806\u6765\u7ef4\u62a4\u8fd9\u4e2a”K\u90091″\u7684\u8fc7\u7a0b\u3002<\/p>\n
\n
\n
<\/div>\n<\/div>\n
cpp<\/div>\n
\n
ListNode* mergeKLists(vector<ListNode*>& lists) {\r\n    \/\/ \u5c0f\u6839\u5806\uff1a\u6bd4\u8f83\u8282\u70b9\u503c\r\n    auto cmp = [](ListNode* a, ListNode* b) {\r\n        return a->val > b->val;  \/\/ \u6ce8\u610f\uff1agreater \u2192 \u5c0f\u6839\u5806\r\n    };\r\n    priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp);\r\n\r\n    \/\/ \u628a\u6bcf\u6761\u94fe\u8868\u7684\u5934\u8282\u70b9\u5165\u5806\r\n    for (ListNode* node : lists) {\r\n        if (node) pq.push(node);\r\n    }\r\n\r\n    ListNode dummy(0);\r\n    ListNode* tail = &dummy;\r\n\r\n    while (!pq.empty()) {\r\n        ListNode* node = pq.top(); pq.pop();\r\n        tail->next = node;\r\n        tail = tail->next;\r\n        if (node->next) pq.push(node->next);  \/\/ \u628a\u540e\u7ee7\u5165\u5806\r\n    }\r\n\r\n    return dummy.next;\r\n}<\/pre>\n
 <\/p>\n<\/div>\n<\/div>\n
\u590d\u6742\u5ea6\uff1a<\/strong> \u65f6\u95f4 O(N log K)\uff0c\u7a7a\u95f4 O(K)\u3002N \u662f\u8282\u70b9\u603b\u6570\uff0c\u6bcf\u4e2a\u8282\u70b9\u8fdb\u51fa\u5806\u4e00\u6b21\uff0c\u6bcf\u6b21\u5806\u64cd\u4f5c O(log K)\u3002<\/p>\n
\n
\u89e3\u6cd5\u4e8c\uff1a\u5206\u6cbb\u5408\u5e76\uff08\u4ee3\u7801\u66f4\u7b80\u6d01\uff0c\u6027\u80fd\u76f8\u540c\uff09\u2b50<\/h4>\n
\u628a K \u6761\u94fe\u8868\u4e24\u4e24\u914d\u5bf9\u5408\u5e76\uff0c\u6bcf\u8f6e\u51cf\u534a\uff0c\u50cf\u5f52\u5e76\u6392\u5e8f\u4e00\u6837\u3002<\/p>\n
\n
\n
<\/div>\n<\/div>\n
cpp<\/div>\n
\n
ListNode* mergeKLists(vector<ListNode*>& lists) {\r\n    int n = lists.size();\r\n    if (n == 0) return nullptr;\r\n\r\n    int step = 1;\r\n    while (step < n) {\r\n        for (int i = 0; i + step < n; i += step * 2) {\r\n            lists[i] = mergeTwoLists(lists[i], lists[i + step]);\r\n        }\r\n        step *= 2;\r\n    }\r\n\r\n    return lists[0];\r\n}<\/pre>\n
 <\/p>\n<\/div>\n<\/div>\n
\u8d70\u4e00\u904d\u4f8b\u5b50\uff08K=4\uff09\uff1a<\/strong><\/p>\n
\n
\n
<\/div>\n<\/div>\n
\n
\u521d\u59cb:   [L0, L1, L2, L3]\r\n\r\nstep=1: L0=merge(L0,L1),  L2=merge(L2,L3)\r\n        \u2192 [L01, L1, L23, L3]\r\n\r\nstep=2: L0=merge(L01,L23)\r\n        \u2192 [L0123, ...]\r\n\r\n\u8fd4\u56de lists[0]<\/pre>\n
 <\/p>\n<\/div>\n<\/div>\n
\u4e3a\u4ec0\u4e48\u4e0d\u80fd\u4e00\u6761\u6761\u987a\u5e8f\u5408\u5e76\uff1f<\/strong><\/p>\n
\n
\n
<\/div>\n<\/div>\n
\n
\u987a\u5e8f\u5408\u5e76: merge(merge(merge(L0,L1), L2), L3)\r\n\u6bcf\u6b21\u5408\u5e76\u7684\u94fe\u8868\u8d8a\u6765\u8d8a\u957f\uff0c\u603b\u4ee3\u4ef7 O(NK)\r\n\r\n\u5206\u6cbb\u5408\u5e76: \u6bcf\u8f6e N \u4e2a\u8282\u70b9\u5404\u88ab\u5408\u5e76\u4e00\u6b21\uff0c\u5171 log K \u8f6e\r\n\u603b\u4ee3\u4ef7 O(N log K)  \u2190 \u5dee\u4e86\u4e00\u4e2a\u6570\u91cf\u7ea7<\/pre>\n
 <\/p>\n<\/div>\n<\/div>\n
\u590d\u6742\u5ea6\uff1a<\/strong> \u65f6\u95f4 O(N log K)\uff0c\u7a7a\u95f4 O(log K)\uff08\u9012\u5f52\u6808\uff0c\u82e5\u7528\u8fed\u4ee3\u7248\u5219 O(1)\uff09\u3002<\/p>\n
\n
\u4e24\u79cd\u6700\u4f18\u89e3\u6cd5\u5bf9\u6bd4<\/h4>\n
\n\n\n\n\n\n\n\n\n\n
<\/th>\n\u6700\u5c0f\u5806<\/th>\n\u5206\u6cbb\u5408\u5e76<\/th>\n<\/tr>\n<\/thead>\n
\u65f6\u95f4<\/td>\nO(N log K)<\/td>\nO(N log K)<\/td>\n<\/tr>\n
\u7a7a\u95f4<\/td>\nO(K)<\/td>\nO(log K) \u6216 O(1)<\/td>\n<\/tr>\n
\u4ee3\u7801\u91cf<\/td>\n\u7a0d\u591a<\/td>\n\u5c11\uff0c\u590d\u7528 mergeTwoLists<\/td>\n<\/tr>\n
\u6269\u5c55\u6027<\/td>\n\u5806\u652f\u6301\u52a8\u6001\u589e\u5220\u94fe\u8868<\/td>\n\u9759\u6001\u5217\u8868\u66f4\u4f18<\/td>\n<\/tr>\n
\u9762\u8bd5\u63a8\u8350<\/td>\n\u8003\u5bdf\u5806\u7684\u4f7f\u7528<\/td>\n\u8003\u5bdf\u5206\u6cbb\u601d\u7ef4<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n
\u4e24\u79cd\u90fd\u8981\u638c\u63e1\uff0c\u9762\u8bd5\u65f6\u5148\u8bf4\u5806\u7684\u601d\u8def\uff0c\u518d\u8bf4\u5206\u6cbb\uff0c\u5c55\u793a\u4f60\u77e5\u9053\u4e24\u79cd\u8def\u5f84\u3002<\/p>\n
\n
\u4e32\u8054\u524d\u9762\u7684\u77e5\u8bc6<\/h4>\n
\u8fd9\u9053\u9898\u662f\u94fe\u8868\u9898\u7684\u7efc\u5408\u9898<\/strong>\uff0c\u878d\u5408\u4e86\uff1a<\/p>\n
    \n
  • \u5408\u5e76\u4e24\u6761\u6709\u5e8f\u94fe\u8868<\/strong>\uff08\u5b50\u95ee\u9898\uff09<\/li>\n
  • \u6700\u5c0f\u5806\/\u4f18\u5148\u961f\u5217<\/strong>\uff08\u9ad8\u6548\u9009\u6700\u5c0f\uff09<\/li>\n
  • \u5206\u6cbb\u601d\u60f3<\/strong>\uff08\u628a O(NK) \u538b\u6210 O(N log K)\uff09<\/li>\n<\/ul>\n
    \u80fd\u628a\u8fd9\u4e09\u70b9\u8bb2\u6e05\u695a\uff0c\u94fe\u8868\u8fd9\u5757\u57fa\u672c\u5c31\u6ca1\u6709\u77ed\u677f\u4e86\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"
    \u529b\u6263\u7b2c 23 \u9898\u3002\u7ed9 K \u6761\u6709\u5e8f\u94fe\u8868\uff0c\u5408<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"colormag_page_container_layout":"default_layout","colormag_page_sidebar_layout":"default_layout","footnotes":""},"categories":[24],"tags":[],"class_list":["post-7401","post","type-post","status-publish","format-standard","hentry","category-value_docs"],"_links":{"self":[{"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/posts\/7401","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/comments?post=7401"}],"version-history":[{"count":1,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/posts\/7401\/revisions"}],"predecessor-version":[{"id":7402,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/posts\/7401\/revisions\/7402"}],"wp:attachment":[{"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/media?parent=7401"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/categories?post=7401"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/tags?post=7401"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}