题目描述
题目链接: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++)
代码如下:
1 | class Solution { |
- 时间复杂度: O(nlgn)
- 空间复杂度: O(1)
GitHub 代码同步地址: 148.SortList.cpp
其他题目:
GitHub: Leetcode-C++-Solution
博客: Leetcode-Solutions