leetcode：148. 排序链表

题目

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

示例 1：
[中等] 148. 排序链表 - 图1

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

示例 2：
[中等] 148. 排序链表 - 图2

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

示例 3：

  1. 输入：head = []
  2. 输出：[]

解答 & 代码

解法一：自顶向下归并排序（递归）

  1. 定位到链表中间节点 mid，将链表拆分成左、右两个子链表
  2. 分别递归排序左子链表、右子链表

  3. 将排序后的左、右子链表合并

    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. private:
    13.  // 寻找链表中间节点并返回
    14.  ListNode* findMidNode(ListNode* head)
    15.  {
    16.      // 注意这里快、慢指针都从虚拟头节点开始遍历，这样偶数节点链表定位到中间节点，奇数节点
    17.      // 链表则定位到第一个中间节点，这样得到的中间节点就可以作为左子节点的最后一个节点。
    18.      // 而如果从 head 开始遍历，奇数节点链表会定位到第二个中间节点，就只能得到右子链表的起点
    19.      ListNode* dummyHead = new ListNode(0, head);
    20.      ListNode* fast = dummyHead;
    21.      ListNode* slow = dummyHead;
    22.      while(fast != nullptr && fast->next != nullptr)
    23.      {
    24.          fast = fast->next->next;
    25.          slow = slow->next;
    26.      }
    27.      return slow;
    28.  }
    30.  // 合并两个有序链表
    31.  ListNode* mergeList(ListNode* head1, ListNode* head2)
    32.  {
    33.      ListNode* dummyHead = new ListNode();
    34.      ListNode* pre = dummyHead;
    35.      ListNode* cur1 = head1;
    36.      ListNode* cur2 = head2;
    37.      while(cur1 != nullptr && cur2 != nullptr)
    38.      {
    39.          if(cur1->val < cur2->val)
    40.          {
    41.              pre->next = cur1;
    42.              pre = cur1;
    43.              cur1 = cur1->next;
    44.          }
    45.          else
    46.          {
    47.              pre->next = cur2;
    48.              pre = cur2;
    49.              cur2 = cur2->next;
    50.          }
    51.      }
    52.      if(cur1 != nullptr)
    53.          pre->next = cur1;
    54.      if(cur2 != nullptr)
    55.          pre->next = cur2;
    56.      return dummyHead->next;
    57.  }
    58. public:
    59.  // 递归归并排序
    60.  ListNode* sortList(ListNode* head) {
    61.      // 递归结束条件：链表为空 or 只有一个节点
    62.      if(head == nullptr || head->next == nullptr)
    63.          return head;
    65.      // 1. 定位到链表中间节点 mid，将链表拆分成左、右两个子链表
    66.      ListNode* mid = findMidNode(head);
    67.      ListNode* rightHead = mid->next;    // 右子链表的头节点
    68.      mid->next = nullptr;                // 将左子链表的尾部指向 nullptr
    69.      // 2. 分别递归排序左子链表、右子链表
    70.      head = sortList(head);
    71.      rightHead = sortList(rightHead);
    72.      // 3. 将排序后的左、右子链表合并
    73.      head = mergeList(head, rightHead);
    74.      return head;
    75.  }
    76. };

    复杂度分析：设链表长为 N

  • 时间复杂度 O(N logN)：归并排序时间复杂度
  • 空间复杂度 O(log N)：递归栈空间复杂度

执行结果：

  1. 执行结果：通过
  3. 执行用时：132 ms, 在所有 C++ 提交中击败了 12.01% 的用户
  4. 内存消耗：59.3 MB, 在所有 C++ 提交中击败了 5.02% 的用户

解法二：自底向上归并排序

[中等] 148. 排序链表
复杂度分析：设链表长为 N

  • 时间复杂度 O(N logN)：
  • 空间复杂度 O(1)：