题目

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

示例

  1. 输入：head = [-1,5,3,4,0]
  2. 输出：[-1,0,3,4,5]

实现

思路1 归并排序

归并排序可以采用自顶向上或者是自顶向下。由于题目要求常数级空间复杂度，所以这里采用自底向上的方法。
image.png

  1. 首先将链表分割成长度为subLen的子链表（初始subLen=1），然后相邻两个子链表进行有序链表的合并（如第21题“合并两个有序链表”），这样就会得到若干个长度为subLen*2的有序子链表。
  2. 将subLen的值加倍然后重复上述循环，直到有序子链表的长度大于等于链表总长度，最终得到的就是排序好的链表。
  1. /**
  2.  * Definition for singly-linked list.
  3.  * struct ListNode {
  4.  *     int val;
  5.  *     ListNode *next;
  6.  *     ListNode() : val(0), next(nullptr) {}
  7.  *     ListNode(int x) : val(x), next(nullptr) {}
  8.  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
  9.  * };
  10.  */
  11. class Solution {
  12. public:
  13.     ListNode* sortList(ListNode* head) {
  14.         if (head == nullptr) {
  15.             return head;
  16.         }
  17.         // 1. 首先统计链表长度
  18.         int length = 0;
  19.         ListNode* node = head;
  20.         while (node != nullptr) {
  21.             length++;
  22.             node = node->next;
  23.         }
  25.         // 2. 引入哨兵节点
  26.         ListNode* dummyHead = new ListNode(0, head);
  28.         // 3. 每次将链表拆分成若干个长度为subLen，两两归并
  29.         for (int subLen = 1; subLen < length; subLen <<= 1) {
  30.             // curr用来记录链表隔断的位置
  31.             ListNode* prev = dummyHead, *curr = dummyHead->next;
  33.             // 开始拆分整个链表
  34.             while (curr != nullptr) {
  35.                 ListNode* head1 = curr;  //第1个长度为subLen的链表头
  36.                 // 3.1 先拆分第1个长度为subLen的链表
  37.                 for (int i = 1; i < subLen && curr->next != nullptr; i++) {
  38.                     curr = curr->next;
  39.                 } // 找到第1个链表的尾部
  42.                 ListNode* head2 = curr->next; // 第2个链表的头，即链表1尾部的下一个节点
  43.                 curr->next = nullptr; // 断开第1个链表和第2个链表的连接
  44.                 curr = head2;
  45.                 // 3.2 再拆分第2个长度为subLen的链表
  46.                 for (int i = 1; i < subLen && curr != nullptr && curr->next != nullptr; i++) {
  47.                     curr = curr->next;
  48.                 } // 找到第2个链表的尾部
  50.                 // 断开第2个链表后面的连接
  51.                 ListNode* next = nullptr; 
  52.                 if (curr != nullptr) {
  53.                     next = curr->next;  // 用来记录两个链表的结束位置
  54.                     curr->next = nullptr;
  55.                 }
  57.                 // 3.3 合并前面拆分得到的两个subLen长度的有序链表
  58.                 ListNode* merged = mergeTwoLists(head1, head2);
  59.                 prev->next = merged;
  61.                 // 将prev移动到subLen*2位置后面，以开始下一轮的拆分
  62.                 while (prev->next != nullptr) {  
  63.                     prev = prev->next;
  64.                 }
  65.                 curr = next;
  66.             }
  67.         }
  68.         return dummyHead->next;
  69.     }
  71.     ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
  72.         ListNode* head = new ListNode(-1);  // 建立新的头用来保存合并后的链表
  73.         ListNode* tail = head;   // 记录新链表的尾部
  74.         while(l1 != nullptr && l2 != nullptr) {
  75.             if(l1->val < l2->val) {
  76.                 tail->next = l1;
  77.                 l1 = l1->next;
  78.             } else {
  79.                 tail->next = l2;
  80.                 l2 = l2->next;
  81.             }
  82.             tail = tail->next;
  83.         }
  84.         // 遍历后l1和l2最多只有一个还未被合并完
  85.         // 直接将链表末尾指向未合并完的链表即可
  86.         if(l1 == nullptr) {
  87.             tail->next = l2;
  88.         } else {
  89.             tail->next = l1;
  90.         }
  92.         return head->next;
  93.     }
  94. };

时间复杂度：. 其中n是链表长度。
空间复杂度：.