| Category | Difficulty | Likes | Dislikes |
|---|
| algorithms | Medium (65.90%) | 1948 | - |
Tags
linked-list | sort
Companies
Unknown
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
示例 1：
1
2
| 输入：head = [4,2,1,3]
输出：[1,2,3,4]
|
示例 2：
1
2
| 输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]
|
示例 3：
提示：
- 链表中节点的数目在范围
[0, 5 * 104] 内 -105 <= Node.val <= 105
**进阶：**你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
Discussion | Solution
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
| // @lc code=start
// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
// pub val: i32,
// pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
// #[inline]
// fn new(val: i32) -> Self {
// ListNode {
// next: None,
// val
// }
// }
// }
impl Solution {
/// ## 解题思路
/// 1. 从头至尾遍历链表,依次将各个节点值加入到数组vals中;
/// 2. 排序vals数组;
/// 3. 遍历排序后的vals数组,生成有序的新链表;
pub fn sort_list(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
let mut vals = Vec::new(); //记录个节点值
let mut p = head.as_ref(); //设置遍历指针
while let Some(mut node) = p {
vals.push(node.val);
p = node.next.as_ref();
}
vals.sort(); //对数组进行排序
let mut next = None;
while let Some(val) = vals.pop() {
next = Some(Box::new(ListNode { next, val }));
}
next
}
}
// @lc code=end
|