{"id":923,"date":"2025-12-11T18:06:07","date_gmt":"2025-12-11T10:06:07","guid":{"rendered":"https:\/\/www.guanhaobo.cn\/?p=923"},"modified":"2025-12-11T18:06:07","modified_gmt":"2025-12-11T10:06:07","slug":"leetcode-148-%e6%8e%92%e5%ba%8f%e9%93%be%e8%a1%a8","status":"publish","type":"post","link":"https:\/\/www.guanhaobo.cn\/?p=923","title":{"rendered":"LeetCode 148 \u2014 \u6392\u5e8f\u94fe\u8868"},"content":{"rendered":"

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

\u7ed9\u4f60\u94fe\u8868\u7684\u5934\u7ed3\u70b9 head \uff0c\u8bf7\u5c06\u5176\u6309 \u5347\u5e8f \u6392\u5217\u5e76\u8fd4\u56de \u6392\u5e8f\u540e\u7684\u94fe\u8868 \u3002
\n\u8f93\u5165\uff1ahead = [4,2,1,3]
\n\u8f93\u51fa\uff1a[1,2,3,4]<\/p>\n

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

\u53ef\u4ee5\u4f7f\u7528 ArrayList \u6216\u8005 PriorityQueue \u6765\u5b58\u50a8\u7ed3\u70b9\uff0c\u7136\u540e\u6392\u5e8f\uff0c\u65f6\u95f4\u590d\u6742\u5ea6 O(n * logn)\uff0c\u4f46\u90fd\u9700\u8981\u989d\u5916\u5f00\u8f9f\u7a7a\u95f4 O(n)<\/p>\n

\u5982\u679c\u4e0d\u989d\u5916\u5f00\u8f9f\u7a7a\u95f4\uff0c\u5219\u53ef\u4ee5\u5f52\u5e76\u6392\u5e8f\uff1a
\n1. \u627e\u51fa\u94fe\u8868\u4e2d\u70b9\uff0c\u5c06\u94fe\u8868\u5206\u4e3a2\u4e2a\u5b50\u94fe\u8868
\n2. \u9012\u5f52\u8c03\u7528\uff0c\u5bf9\u5b50\u94fe\u8868\u8fdb\u884c\u6392\u5e8f
\n3. \u5408\u5e76\u4e24\u4e2a\u5b50\u94fe\u8868
\n\u65f6\u95f4\u590d\u6742\u5ea6 O(n * logn)<\/p>\n

Java<\/h1>\n
public ListNode sortList(ListNode head) {\n    \/\/ \u9012\u5f52\u51fa\u53e3\n    if (head == null || head.next == null) {\n        return head;\n    }\n\n    \/\/ \u627e\u51fa\u4e2d\u70b9\n    ListNode p1 = head, p2 = head.next;\n    ListNode mid = head;\n    while (p2 != null && p2.next != null) {\n        mid = p1;\n        p1 = p1.next;\n        p2 = p2.next;\n        p2 = p2.next;\n    }\n\n    \/\/ \u9012\u5f52\u6392\u5e8f\u5b50\u94fe\u8868\n    ListNode left = head;\n    ListNode right = mid.next;\n    mid.next = null;\n    left = sortList(left);\n    right = sortList(right);\n\n    \/\/ \u5408\u5e76\u5de6\u53f3\u5b50\u94fe\u8868\n    ListNode ans = new ListNode();\n    ListNode cur = ans;\n    while (left != null && right != null) {\n        if (left.val < right.val) {\n            cur.next = left;\n            left = left.next;\n        } else {\n            cur.next = right;\n            right = right.next;\n        }\n        cur = cur.next;\n    }\n    if (left != null) {\n        cur.next = left;\n    }\n    if (right != null) {\n        cur.next = right;\n    }\n\n    return ans.next;\n}\n<\/code><\/pre>\n
Kotlin<\/h1>\n
fun sortList(head: ListNode?): ListNode? {\n    \/\/ \u9012\u5f52\u51fa\u53e3\n    if (head?.next == null) {\n        return head\n    }\n\n\n    \/\/ \u5bfb\u627e\u4e2d\u70b9\n    var slow = head!!\n    var fast = head.next\n    while (fast?.next != null) {\n        slow = slow.next!!\n        fast = fast.next?.next\n    }\n\n    \/\/ \u9012\u5f52\u6392\u5e8f\u5b50\u94fe\u8868\n    var left = head\n    val mid = slow\n    var right = mid.next\n    mid.next = null\n    left = sortList(left)\n    right = sortList(right)\n\n    \/\/ \u5408\u5e76\u5b50\u94fe\u8868\n    val ans = ListNode(0)\n    var cur = ans\n    while (left != null && right != null) {\n        if (left.`val` < right.`val`) {\n            cur.next = left\n            left = left.next\n        } else {\n            cur.next = right\n            right = right.next\n        }\n        cur = cur.next!!\n    }\n    if (left != null) {\n        cur.next = left;\n    }\n    if (right != null) {\n        cur.next = right;\n    }\n\n    return ans.next\n}\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
\u9898\u76ee\u63cf\u8ff0 \u7ed9\u4f60\u94fe\u8868\u7684\u5934\u7ed3\u70b9 head \uff0c\u8bf7\u5c06\u5176\u6309 \u5347\u5e8f \u6392\u5217\u5e76\u8fd4\u56de \u6392\u5e8f\u540e\u7684\u94fe\u8868 \u3002 \u8f93\u5165\uff1ahead = [4 […]<\/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,81,75,51,64,84],"class_list":["post-923","post","type-post","status-publish","format-standard","hentry","category-algo","tag-leetcode","tag-81","tag-75","tag-51","tag-64","tag-84"],"_links":{"self":[{"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/posts\/923","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=923"}],"version-history":[{"count":1,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/posts\/923\/revisions"}],"predecessor-version":[{"id":924,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/posts\/923\/revisions\/924"}],"wp:attachment":[{"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=923"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=923"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=923"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}