0%

[Leetcode]148. Sort List(C++)

题目描述

题目链接: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 and O(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++)

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
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