leetcode148_排序链表的3种解法

• 1. 题目
• 2. 解答
  • 2.1. 解法1
  • 2.2. 解法2
  • 2.3. 解法3

1. 题目

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

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* sortList(ListNode* head) {}
};

样例：

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

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

输入：head = []
输出：[]

提示：

链表中节点的数目在范围 [0, 5 * 104] 内
-105 <= Node.val <= 105

进阶：

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

2. 解答

2.1. 解法1

把链表中每个节点的val保存到一个额外的数组里，对数组进行排序，最后把数组里的值依次复制到链表的各个节点。

class Solution {
public:ListNode* sortList(ListNode* head) {vector<int> vi;ListNode *curNode = head;while (curNode) {vi.push_back(curNode->val);curNode = curNode->next;}sort(vi.begin(), vi.end());auto it = vi.begin();curNode = head;while (curNode) {curNode->val = *it;curNode = curNode->next;++it;}return head;}
};

时间复杂度：O(nlogn)。性能瓶颈是sort函数的时间复杂度。
空间复杂度：O(n)，额外分配的数组跟链表是一个数量级的。

2.2. 解法2

自顶向下归并排序。

1. 通过快慢指针把链表分割成两部分。
2. 递归分别排序两个子链表。
3. 使用归并排序的思路合并两个子链表。

class Solution {
public:ListNode* sortList(ListNode* head) {if (!head || !head->next) {return head;}ListNode *firstBegin = head;ListNode *firstEnd = head;ListNode *secondEnd = head->next;while (firstEnd && secondEnd) {if (secondEnd->next) {secondEnd = secondEnd->next->next;} else {break;}firstEnd = firstEnd->next;}ListNode *secondBegin = firstEnd->next;firstEnd->next = nullptr;ListNode *firstList = sortList(firstBegin);ListNode *secondList = sortList(secondBegin);return MergeList(firstList, secondList);}private:ListNode *MergeList(ListNode *firstList, ListNode *secondList){ListNode *fList = firstList;ListNode *sList = secondList;ListNode *list = new ListNode();ListNode *cur = list;while (fList && sList) {if (fList->val <= sList->val) {cur->next = fList;fList = fList->next;} else {cur->next = sList;sList = sList->next;}cur = cur->next;}cur->next = fList ? fList : sList;cur = list->next;delete list;return cur;}
};

时间复杂度：O(nlogn)。
空间复杂度：O(logn)，虽然是对链表做原地改动，但递归调用的栈空间达到了O(logn)的空间复杂度。

虽然递归函数是自顶向下调用的，但它是自底向上返回的，因此需要栈空间保存一部分数据。

2.3. 解法3

自底向上归并排序。使用迭代代替递归，自底向上逐级排序。

1. 将整个链表分成数个长度为1的子链表，每个子链表都是有序的。
2. 将链表中相邻的每两个长度为1的子链表合并成一个长度为2的有序的子链表。
3. 将链表中相邻的每两个长度为2的子链表合并成一个长度为4的有序的子链表。
4. 以此类推，直到子链表的长度等于初始链表的长度。

class Solution {
public:ListNode* sortList(ListNode* head) {ListNode *curNode = head;int length = 0;while (curNode) {curNode = curNode->next;++length;}ListNode *mergedList = new ListNode(0, head);for (int subLength = 1; subLength <= length; subLength <<= 1) {curNode = mergedList->next;ListNode *mergedCur = mergedList;while (curNode) {ListNode *head1 = curNode;ListNode *tail1 = GetList(head1, subLength);if (!tail1) {// head1一定是有序的mergedCur->next = head1;break;}ListNode *head2 = tail1->next;tail1->next = nullptr;ListNode *tail2 = GetList(head2, subLength);if (tail2) {curNode = tail2->next;tail2->next = nullptr;}mergedCur->next = MergeList(head1, head2);while (mergedCur->next) {mergedCur = mergedCur->next;}if (!tail2) {break;}}}curNode = mergedList->next;delete mergedList;return curNode;}private:// 以head为第一个元素，获取长度为length的链表，返回最后一个元素的地址。// 如果返回nullptr说明获取的链表长度不足lengthListNode *GetList(ListNode *head, int length){ListNode *cur = head;for (int i = 1; i < length && cur; ++i) {cur = cur->next;}return cur;}ListNode *MergeList(ListNode *firstList, ListNode *secondList){ListNode *fList = firstList;ListNode *sList = secondList;ListNode *list = new ListNode();ListNode *cur = list;while (fList && sList) {if (fList->val <= sList->val) {cur->next = fList;fList = fList->next;} else {cur->next = sList;sList = sList->next;}cur = cur->next;}cur->next = fList ? fList : sList;cur = list->next;delete list;return cur;}
};

时间复杂度：O(nlogn)，sortList里for循环的时间复杂度是O(logn)，它内嵌的while循环复杂度是O(n)，相乘为O(nlogn)。
空间复杂度：O(1)。只额外分配了常数级的变量，无递归开销。