Sort List

描述

Sort a linked list in O(n log n) time using constant space complexity.

分析

常数空间且O(nlogn)，单链表适合用归并排序，双向链表适合用快速排序。本题可以复用 Merge Two Sorted Lists 的代码。

代码

  1. // Sort List
  2. // 归并排序，时间复杂度O(nlogn)，空间复杂度O(1)
  3. class Solution {
  4. public:
  5.     ListNode *sortList(ListNode *head) {
  6.         if (head == NULL || head->next == NULL)return head;
  8.         ListNode *middle = findMiddle(head);
  9.         ListNode *head2 = middle->next;
  10.         middle->next = nullptr; // 断开
  12.         ListNode *l1 = sortList(head);  // 前半段排序
  13.         ListNode *l2 = sortList(head2);  // 后半段排序
  14.         return mergeTwoLists(l1, l2);
  15.     }
  16. private:
  17.     // Merge Two Sorted Lists
  18.     static ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
  19.         ListNode dummy(-1);
  20.         for (ListNode* p = &dummy; l1 != nullptr || l2 != nullptr; p = p->next) {
  21.             int val1 = l1 == nullptr ? INT_MAX : l1->val;
  22.             int val2 = l2 == nullptr ? INT_MAX : l2->val;
  23.             if (val1 <= val2) {
  24.                 p->next = l1;
  25.                 l1 = l1->next;
  26.             } else {
  27.                 p->next = l2;
  28.                 l2 = l2->next;
  29.             }
  30.         }
  31.         return dummy.next;
  32.     }
  33.     // 快慢指针找到中间节点
  34.     static ListNode* findMiddle(ListNode* head) {
  35.         if (head == nullptr) return nullptr;
  37.         ListNode *slow = head;
  38.         ListNode *fast = head->next;
  40.         while (fast != nullptr && fast->next != nullptr) {
  41.             slow = slow->next;
  42.             fast = fast->next->next;
  43.         }
  44.         return slow;
  45.     }
  46. };

相关题目

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/cpp/sorting/merge-sort/sort-list.html