leetcode/
sort_list.rs

1//! # 21. 合并两个有序链表
2//! 难度 简单
3//!
4//! 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
5//!
6//! ## 示例：
7//!
8//! ```text
9//! 输入：1->2->4, 1->3->4
10//! 输出：1->1->2->3->4->4
11//! ```
12//!
13//! See [leetcode](https://leetcode-cn.com/problems/merge-two-sorted-lists/)
14
15use crate::ListNode;
16
17pub struct Solution;
18
19type List = Option<Box<ListNode>>;
20
21impl Solution {
22
23    /// Bottom Up Merge Sort
24    ///
25    /// ## FIXME
26    /// CANNOT use a raw pointer after value moved
27    pub fn sort_list(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
28        if head.is_none() || head.as_ref().unwrap().next.is_none() {
29            return head;
30        }
31
32        let mut length = 0;
33        let mut node = &head;
34        while node.is_some() {
35            length += 1;
36            node = &node.as_ref().unwrap().next;
37        }
38
39        let mut start = head;
40        let mut size = 1;
41
42        while size < length {
43            let mut linked = Box::new(ListNode::new(0));
44            let mut last_tail: *mut ListNode = &mut *linked;
45
46            while start.is_some() {
47                if start.as_ref().unwrap().next.is_none() {
48                    unsafe {
49                        // link the rest part
50                        (*last_tail).next = start;
51                    }
52                    break;
53                }
54
55                let (first, second, rest) = Self::split_two_at(start, size);
56                let (merged_part, tail) = Self::merge(first, second);
57
58                // link the merged_part list to the linked list
59                unsafe { (*last_tail).next = merged_part; }
60                // update the `last_tail` to the linked's tail
61                last_tail = tail;
62
63                start = rest;
64            }
65            start = linked.next;
66            size = size * 2;
67        }
68
69        start
70    }
71
72    /// merge two list, returning the merged list and the tail raw pointer of it, to prevent seek again
73    fn merge(mut list1: List, mut list2: List) -> (List, *mut ListNode) {
74        let mut dummy_head = Box::new(ListNode::new(0));
75        let mut new_tail = &mut dummy_head;
76        while list1.is_some() && list2.is_some() {
77            if list1.as_ref().unwrap().val < list2.as_ref().unwrap().val {
78                new_tail.next = list1.take();
79                list1 = new_tail.next.as_mut().unwrap().next.take();
80            } else {
81                new_tail.next = list2.take();
82                list2 = new_tail.next.as_mut().unwrap().next.take();
83            }
84            new_tail = new_tail.next.as_mut().unwrap();
85        }
86
87        new_tail.next = if list1.is_some() {
88            list1
89        } else {
90            list2
91        };
92
93        while new_tail.next.is_some() {
94            new_tail = new_tail.next.as_mut().unwrap();
95        }
96
97        // FIXME CANNOT use a raw pointer after value moved
98        // `new_tail: Box<ListNode>` so its location would not be changed
99        let tail_ptr: *mut ListNode = &mut **new_tail;
100
101        (dummy_head.next, tail_ptr)
102    }
103
104    /// split a list into two sub list at the `at` index of the rest list,
105    /// returning the (firist, second, rest)
106    fn split_two_at(head: List, at: usize) -> (List, List, List) {
107        if head.is_none() {
108            return (None, None, None);
109        }
110
111        let mut head = head.unwrap();
112        // because we need two mutable pointers, so here we have to use unsafe block,
113        // but they are guaranteed safe here.
114        unsafe {
115            let mut slow: *mut ListNode = &mut *head;
116            let mut fast: *mut ListNode = &mut **(*slow).next.as_mut().unwrap();
117            let mut i = 1;
118            while i < at && ((*fast).next.is_some() || (*slow).next.is_some()) {
119                if (*slow).next.is_some() {
120                    slow = &mut **(*slow).next.as_mut().unwrap();
121                }
122                if (*fast).next.is_some() {
123                    if (*fast).next.as_ref().unwrap().next.is_some() {
124                        fast = &mut **(*fast).next.as_mut().unwrap().next.as_mut().unwrap();
125                    } else {
126                        fast = &mut **(*fast).next.as_mut().unwrap();
127                    }
128                }
129                i += 1;
130            }
131            (Some(head), (*slow).next.take(), (*fast).next.take())
132        }
133    }
134}
leetcode/sort_list.rs

leetcode/
sort_list.rs
