对链表进行插入排序,
从链表第一个元素开始可以视为部分已排序,每次操作从链表中移除一个元素,然后原地将移除的元素插入到已排好序的部分。
数据范围:链表长度满足 ,链表中每个元素满足
例如输入{2,4,1}时,对应的返回值为{1,2,4},转换过程如下图所示:
/** * #[derive(PartialEq, Eq, Debug, Clone)] * pub struct ListNode { * pub val: i32, * pub next: Option<Box<ListNode>> * } * * impl ListNode { * #[inline] * fn new(val: i32) -> Self { * ListNode { * val: val, * next: None, * } * } * } */ struct Solution{ } impl Solution { fn new() -> Self { Solution{} } /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param head ListNode类 * @return ListNode类 */ pub fn insertionSortList(&self, head: Option<Box<ListNode>>) -> Option<Box<ListNode>> { // write code here // let mut ordered_num = 0; let mut dummy_head_new = Some(Box::new(ListNode::new(233))); let mut dummy_head = Some(ListNode::new(233)); dummy_head.as_mut()?.next = head; // let ordered_list = None; let mut p = &mut dummy_head; while p.as_ref()?.next.is_some() { let mut node = p.as_mut()?.next.take(); p.as_mut()?.next = node.as_mut()?.next.take(); let mut p_insert_next = &mut dummy_head_new; while p_insert_next.as_ref()?.next.is_some() && p_insert_next.as_ref()?.next.as_ref()?.val <= node.as_ref()?.val { p_insert_next = &mut p_insert_next.as_mut()?.next; } node.as_mut()?.next = p_insert_next.as_mut()?.next.take(); p_insert_next.as_mut()?.next = node; } // todo!(); dummy_head_new?.next } }