题目描述
题目链接:148. Sort List
Given the
head
of a linked list, return the list after sorting it in ascending order.
例子
例子 1
Input:
head = [4,2,1,3]
Output:[1,2,3,4]
例子 2
Input:
head = [-1,5,3,4,0]
Output:[-1,0,3,4,5]
例子 3
Input:
head = []
Output:[]
Follow Up
- Can you sort the linked list in
O(n logn)
time andO(1)
memory (i.e. constant space)?
Constraints
- The number of nodes in the list is in the range
[0, 5 * 10^4]
.-10^5 <= Node.val <= 10^5
解题思路
题目要求在 O(nlogn)
的时间复杂度下对链表排序,不难想到可以使用归并排序,由于是链表所以可以自由控制节点的位置,无需使用额外空间。归并算法的思路是对链表首先分半,对前后两半递归使用排序,将排好序的链表合并在一起就行。合并排好序的链表很简单,可以参考:[Leetcode]21. Merge Two Sorted Lists(C++)
代码如下:
class Solution {
public:
ListNode* sortList(ListNode* head) {
// for linked list with length of 0 or 1, no need to sort
if (!head || !head->next) {
return head;
}
ListNode *dummy = new ListNode();
dummy->next = head;
ListNode *fast = dummy;
ListNode *slow = dummy;
while (fast && fast->next) {
fast = fast->next->next;
slow = slow->next;
}
fast = slow->next;
slow->next = nullptr;
return merge(sortList(head), sortList(fast));
}
private:
ListNode* merge(ListNode *A, ListNode *B) {
ListNode *dummy = new ListNode();
ListNode *curr = dummy;
while (A && B) {
if (A->val <= B->val) {
curr->next = A;
A = A->next;
} else {
curr->next = B;
B = B->next;
}
curr = curr->next;
}
if (!A) {
curr->next = B;
}
if (!B) {
curr->next = A;
}
return dummy->next;
}
};
- 时间复杂度: O(nlgn)
- 空间复杂度: O(1)
GitHub 代码同步地址: 148.SortList.cpp
其他题目: GitHub: Leetcode-C++-Solution 博客: Leetcode-Solutions