{"id":914,"date":"2025-10-26T17:57:17","date_gmt":"2025-10-26T09:57:17","guid":{"rendered":"https:\/\/www.guanhaobo.cn\/?p=914"},"modified":"2025-10-26T17:57:17","modified_gmt":"2025-10-26T09:57:17","slug":"leetcode-143-%e9%87%8d%e6%8e%92%e9%93%be%e8%a1%a8","status":"publish","type":"post","link":"https:\/\/www.guanhaobo.cn\/?p=914","title":{"rendered":"LeetCode 143 \u2013 \u91cd\u6392\u94fe\u8868"},"content":{"rendered":"

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

\u7ed9\u5b9a\u4e00\u4e2a\u5355\u94fe\u8868 L \u7684\u5934\u8282\u70b9 head \uff0c\u5355\u94fe\u8868 L \u8868\u793a\u4e3a\uff1a<\/p>\n

L0 \u2192 L1 \u2192 \u2026 \u2192 Ln – 1 \u2192 Ln
\n\u8bf7\u5c06\u5176\u91cd\u65b0\u6392\u5217\u540e\u53d8\u4e3a\uff1a<\/p>\n

L0 \u2192 Ln \u2192 L1 \u2192 Ln – 1 \u2192 L2 \u2192 Ln – 2 \u2192 \u2026
\n\u4e0d\u80fd\u53ea\u662f\u5355\u7eaf\u7684\u6539\u53d8\u8282\u70b9\u5185\u90e8\u7684\u503c\uff0c\u800c\u662f\u9700\u8981\u5b9e\u9645\u7684\u8fdb\u884c\u8282\u70b9\u4ea4\u6362\u3002<\/p>\n

\u793a\u4f8b\uff1a
\n\"\"<\/a>
\n\u8f93\u5165\uff1ahead = [1,2,3,4,5]
\n\u8f93\u51fa\uff1a[1,5,2,4,3]<\/p>\n

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

\u5148\u627e\u5230\u4e2d\u70b9\uff0c\u628a\u94fe\u8868\u62c6\u5206\u4e3a2\u4e2a\uff0c\u628a\u540e\u9762\u7684\u94fe\u8868\u53cd\u8f6c\uff0c\u6700\u540e\u518d\u5c062\u4e2a\u94fe\u8868\u5408\u5e76\u3002
\n\u7a7a\u95f4\u590d\u6742\u5ea6 O(1)<\/p>\n

Java<\/h1>\n
public void reorderList(ListNode head) {\n    ListNode midNode = getMidNode(head);\n    ListNode p1 = head, p2 = midNode.next;\n    midNode.next = null;\n    p2 = reverse(p2);\n    merge(p1, p2);\n}\n\nprivate ListNode getMidNode(ListNode head) {\n    if (head == null) {\n        return null;\n    }\n    ListNode slow = head, fast = head.next;\n    while (fast != null && fast.next != null) {\n        slow = slow.next;\n        fast = fast.next.next;\n    }\n    return slow;\n}\n\nprivate ListNode reverse(ListNode head) {\n    ListNode pre = null;\n    while (head != null) {\n        ListNode temp = head.next;\n        head.next = pre;\n        pre = head;\n        head = temp;\n    }\n    return pre;\n}\n\nprivate void merge(ListNode p1, ListNode p2) {\n    while (p1 != null && p2 != null) {\n        ListNode next1 = p1.next;\n        ListNode next2 = p2.next;\n        p1.next = p2;\n        if (next1 != null) {\n            p2.next = next1;\n        }\n        p1 = next1;\n        p2 = next2;\n    }\n}\n<\/code><\/pre>\n
Kotlin<\/h1>\n
fun reorderList(head: ListNode?): Unit {\n    if (head == null) {\n        return\n    }\n    val midNode = getMidNode(head)\n    val p1 = head\n    val p2 = reverse(midNode.next)\n    midNode.next = null\n    merge(p1, p2)\n}\n\nprivate fun getMidNode(head: ListNode): ListNode {\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    return slow\n}\n\nprivate fun reverse(head: ListNode?): ListNode? {\n    var pre: ListNode? = null\n    var cur = head\n    while (cur != null) {\n        val temp = cur.next\n        cur.next = pre\n        pre = cur\n        cur = temp\n    }\n    return pre\n}\n\nprivate fun merge(p1: ListNode?, p2: ListNode?) {\n    var cur1 = p1\n    var cur2 = p2\n    while (cur1 != null && cur2 != null) {\n        val next1 = cur1.next\n        val next2 = cur2.next\n        cur1.next = cur2\n        if (next1 != null) {\n            cur2.next = next1\n        }\n        cur1 = next1\n        cur2 = next2\n    }\n}\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
\u9898\u76ee\u63cf\u8ff0 \u7ed9\u5b9a\u4e00\u4e2a\u5355\u94fe\u8868 L \u7684\u5934\u8282\u70b9 head \uff0c\u5355\u94fe\u8868 L \u8868\u793a\u4e3a\uff1a L0 \u2192 L1 \u2192 \u2026 \u2192 Ln & […]<\/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,75,54,84],"class_list":["post-914","post","type-post","status-publish","format-standard","hentry","category-algo","tag-leetcode","tag-75","tag-54","tag-84"],"_links":{"self":[{"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/posts\/914","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=914"}],"version-history":[{"count":1,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/posts\/914\/revisions"}],"predecessor-version":[{"id":915,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/posts\/914\/revisions\/915"}],"wp:attachment":[{"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=914"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=914"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=914"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}