148. Sort List Medium

1/**
2 * [148] Sort List
3 *
4 * Given the head of a linked list, return the list after sorting it in ascending order.
5 *  
6 * Example 1:
7 * <img alt="" src="https://assets.leetcode.com/uploads/2020/09/14/sort_list_1.jpg" style="width: 450px; height: 194px;" />
8 * Input: head = [4,2,1,3]
9 * Output: [1,2,3,4]
10 * 
11 * Example 2:
12 * <img alt="" src="https://assets.leetcode.com/uploads/2020/09/14/sort_list_2.jpg" style="width: 550px; height: 184px;" />
13 * Input: head = [-1,5,3,4,0]
14 * Output: [-1,0,3,4,5]
15 * 
16 * Example 3:
17 * 
18 * Input: head = []
19 * Output: []
20 * 
21 *  
22 * Constraints:
23 * 
24 * 	The number of nodes in the list is in the range [0, 5 * 10^4].
25 * 	-10^5 <= Node.val <= 10^5
26 * 
27 *  
28 * Follow up: Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?
29 * 
30 */
31pub struct Solution {}
32use crate::util::linked_list::{ListNode, to_list};
33
34// problem: https://leetcode.com/problems/sort-list/
35// discuss: https://leetcode.com/problems/sort-list/discuss/?currentPage=1&orderBy=most_votes&query=
36
37// submission codes start here
38
39// Definition for singly-linked list.
40// #[derive(PartialEq, Eq, Clone, Debug)]
41// pub struct ListNode {
42//   pub val: i32,
43//   pub next: Option<Box<ListNode>>
44// }
45// 
46// impl ListNode {
47//   #[inline]
48//   fn new(val: i32) -> Self {
49//     ListNode {
50//       next: None,
51//       val
52//     }
53//   }
54// }
55impl Solution {
56    pub fn sort_list(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
57        Some(Box::new(ListNode::new(0)))
58    }
59}
60
61// submission codes end
62
63#[cfg(test)]
64mod tests {
65    use super::*;
66
67    #[test]
68    fn test_148() {
69    }
70}
71