{"id":3320,"date":"2018-07-26T21:57:00","date_gmt":"2018-07-27T04:57:00","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=3320"},"modified":"2018-09-06T08:41:38","modified_gmt":"2018-09-06T15:41:38","slug":"leetcode-148-sort-list","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/divide-and-conquer\/leetcode-148-sort-list\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 148. Sort List"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 148. Sort List - \u5237\u9898\u627e\u5de5\u4f5c EP211\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/M1TwY0nsTZA?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe><\/p>\n<h1><strong>Problem<\/strong><\/h1>\n<p>Sort a linked list in\u00a0<em>O<\/em>(<em>n<\/em>\u00a0log\u00a0<em>n<\/em>) time using constant space complexity.<\/p>\n<p><strong>Example 1:<\/strong><\/p>\n<pre class=\"crayon:false \"><strong>Input:<\/strong> 4-&gt;2-&gt;1-&gt;3\r\n<strong>Output:<\/strong> 1-&gt;2-&gt;3-&gt;4\r\n<\/pre>\n<p><strong>Example 2:<\/strong><\/p>\n<pre class=\"crayon:false\"><strong>Input:<\/strong> -1-&gt;5-&gt;3-&gt;4-&gt;0\r\n<strong>Output:<\/strong> -1-&gt;0-&gt;3-&gt;4-&gt;5<\/pre>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-3330\" style=\"font-size: 16px;\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/07\/148-ep211.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/07\/148-ep211.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/07\/148-ep211-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/07\/148-ep211-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-3329\" style=\"font-size: 16px;\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/07\/148-ep211-2.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/07\/148-ep211-2.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/07\/148-ep211-2-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/07\/148-ep211-2-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/p>\n<h1>Solution: Merge Sort<\/h1>\n<p>Top-down (recursion)<\/p>\n<p>Time complexity: O(nlogn)<\/p>\n<p>Space complexity: O(logn)<\/p>\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:c++ decode:true \">\/\/ Author: Huahua\r\n\/\/ Running time: 32 ms\r\n\/**\r\n * Definition for singly-linked list.\r\n * struct ListNode {\r\n *     int val;\r\n *     ListNode *next;\r\n *     ListNode(int x) : val(x), next(NULL) {}\r\n * };\r\n *\/\r\nclass Solution {\r\npublic:\r\n  ListNode* sortList(ListNode* head) {\r\n    \/\/ 0 or 1 element, we are done.\r\n    if (!head || !head-&gt;next) return head;\r\n    ListNode* slow = head;\r\n    ListNode* fast = head-&gt;next;    \r\n    while (fast &amp;&amp; fast-&gt;next) {\r\n      fast = fast-&gt;next-&gt;next;\r\n      slow = slow-&gt;next;\r\n    }\r\n    ListNode* mid = slow-&gt;next;    \r\n    slow-&gt;next = nullptr; \/\/ Break the list.\r\n    return merge(sortList(head), sortList(mid));\r\n  }\r\nprivate:\r\n  ListNode* merge(ListNode* l1, ListNode* l2) {\r\n    ListNode dummy(0);\r\n    ListNode* tail = &amp;dummy;\r\n    while (l1 &amp;&amp; l2) {\r\n      if (l1-&gt;val &gt; l2-&gt;val) swap(l1, l2);\r\n      tail-&gt;next = l1;\r\n      l1 = l1-&gt;next;\r\n      tail = tail-&gt;next;\r\n    }\r\n    tail-&gt;next = l1 ? l1 : l2;    \r\n    return dummy.next;\r\n  }\r\n};<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Java<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:java decode:true\">\/\/ Author: Huahua\r\n\/\/ Running time: 6 ms\r\nclass Solution {\r\n  public ListNode sortList(ListNode head) {\r\n    if (head == null || head.next == null) return head;\r\n    ListNode slow = head;\r\n    ListNode fast = head.next;\r\n    while (fast != null &amp;&amp; fast.next != null) {\r\n      fast = fast.next.next;\r\n      slow = slow.next;\r\n    }\r\n    ListNode mid = slow.next;\r\n    slow.next = null;\r\n    return merge(sortList(head), sortList(mid));\r\n  }\r\n  \r\n  private ListNode merge(ListNode l1, ListNode l2) {\r\n    ListNode dummy = new ListNode(0);\r\n    ListNode tail = dummy;\r\n    while (l1 != null &amp;&amp; l2 != null) {\r\n      if (l1.val &gt; l2.val) {\r\n        ListNode tmp = l1;\r\n        l1 = l2;\r\n        l2 = tmp;\r\n      }\r\n      tail.next = l1;\r\n      l1 = l1.next;\r\n      tail = tail.next;\r\n    }\r\n    tail.next = (l1 != null) ? l1 : l2;\r\n    return dummy.next;\r\n  }\r\n}<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Python3<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:python decode:true \"># Author: Huahua, 232 ms\r\nclass Solution:\r\n  def sortList(self, head):\r\n    def merge(l1, l2):\r\n      dummy = ListNode(0)\r\n      tail = dummy\r\n      while l1 and l2:\r\n        if l1.val &gt; l2.val: l1, l2 = l2, l1\r\n        tail.next = l1\r\n        l1 = l1.next\r\n        tail = tail.next\r\n      tail.next = l1 if l1 else l2\r\n      return dummy.next\r\n    \r\n    if not head or not head.next: return head\r\n    slow = head\r\n    fast = head.next\r\n    while fast and fast.next:\r\n      fast = fast.next.next\r\n      slow = slow.next\r\n    mid = slow.next\r\n    slow.next = None\r\n    return merge(self.sortList(head), self.sortList(mid))<\/pre>\n<p>&nbsp;<\/p>\n<\/div><\/div>\n<p>bottom up<\/p>\n<p>Time complexity: O(nlogn)<\/p>\n<p>Space complexity: O(1)<\/p>\n<pre class=\"lang:c++ decode:true \">\/\/ Author: Huahua\r\n\/\/ Running time: 32 ms\r\nclass Solution {\r\npublic:\r\n  ListNode* sortList(ListNode* head) {\r\n    \/\/ 0 or 1 element, we are done.\r\n    if (!head || !head-&gt;next) return head;\r\n    \r\n    int len = 1;\r\n    ListNode* cur = head;\r\n    while (cur = cur-&gt;next) ++len;\r\n    \r\n    ListNode dummy(0);\r\n    dummy.next = head;\r\n    ListNode* l;\r\n    ListNode* r;\r\n    ListNode* tail;\r\n    for (int n = 1; n &lt; len; n &lt;&lt;= 1) {      \r\n      cur = dummy.next; \/\/ partial sorted head\r\n      tail = &amp;dummy;\r\n      while (cur) {\r\n        l = cur;\r\n        r = split(l, n);\r\n        cur = split(r, n);\r\n        auto merged = merge(l, r);\r\n        tail-&gt;next = merged.first;\r\n        tail = merged.second;\r\n      }\r\n    }      \r\n    return dummy.next;\r\n  }\r\nprivate:\r\n  \/\/ Splits the list into two parts, first n element and the rest.\r\n  \/\/ Returns the head of the rest.\r\n  ListNode* split(ListNode* head, int n) {    \r\n    while (--n &amp;&amp; head)\r\n      head = head-&gt;next;\r\n    ListNode* rest = head ? head-&gt;next : nullptr;\r\n    if (head) head-&gt;next = nullptr;\r\n    return rest;\r\n  }\r\n  \r\n  \/\/ Merges two lists, returns the head and tail of the merged list.\r\n  pair&lt;ListNode*, ListNode*&gt; merge(ListNode* l1, ListNode* l2) {\r\n    ListNode dummy(0);\r\n    ListNode* tail = &amp;dummy;\r\n    while (l1 &amp;&amp; l2) {\r\n      if (l1-&gt;val &gt; l2-&gt;val) swap(l1, l2);\r\n      tail-&gt;next = l1;\r\n      l1 = l1-&gt;next;\r\n      tail = tail-&gt;next;\r\n    }\r\n    tail-&gt;next = l1 ? l1 : l2;\r\n    while (tail-&gt;next) tail = tail-&gt;next;\r\n    return {dummy.next, tail};\r\n  }\r\n};<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Problem Sort a linked list in\u00a0O(n\u00a0log\u00a0n) time using constant space complexity. Example 1: Input: 4-&gt;2-&gt;1-&gt;3 Output: 1-&gt;2-&gt;3-&gt;4 Example 2: Input: -1-&gt;5-&gt;3-&gt;4-&gt;0 Output: -1-&gt;0-&gt;3-&gt;4-&gt;5 Solution: Merge&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[43,50],"tags":[352,83,177,321,23],"class_list":["post-3320","post","type-post","status-publish","format-standard","hentry","category-divide-and-conquer","category-list","tag-fast-slow","tag-list","tag-medium","tag-mergesort","tag-sort","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3320","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=3320"}],"version-history":[{"count":8,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3320\/revisions"}],"predecessor-version":[{"id":3881,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3320\/revisions\/3881"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=3320"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=3320"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=3320"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}