2020/2/24

题目描述

• 在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

示例

示例 1:
输入: 4->2->1->3
输出: 1->2->3->4

示例 2:
输入: -1->5->3->4->0
输出: -1->0->3->4->5

相关标签

链表
排序

解题思路

• 迭代法
  算法：
  
  自底向上实现归并排序
  
  本题可以把问题分解为归并+两个有序链表合并（问题 #21）。相比于自顶向下的递归实现，迭代法可以做到O(1) 空间复杂度。递归法这里不再赘述。
  复杂度分析：
  时间复杂度：O(N*logN)，归并会一共产生logN次的分组，分组最大遍历次数为N。
  空间复杂度：O(1）不需要额外空间

源代码

迭代法

    //迭代法
   impl Solution {
    pub fn merge_two_lists(mut l1: Option<Box<ListNode>>, mut l2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {        
        let mut head = Some(Box::new(ListNode::new(0)));
        let (mut p1, mut p2, mut pr) = (&mut l1 as *mut Option<Box<ListNode>>, 
                                        &mut l2 as *mut Option<Box<ListNode>>, 
                                        &mut head as *mut Option<Box<ListNode>>);

        unsafe {
            let node_val = |x: *mut Option<Box<ListNode>>| {
                if *x == None {
                    None
                }else {
                    Some((*x).as_ref().unwrap().val)
                }
            };

            let node_next = |x: *mut Option<Box<ListNode>>| {
                if *x == None {
                    x
                }else {
                    &mut (*x).as_mut().unwrap().next as *mut Option<Box<ListNode>>
                }
            };

            loop {
                match (node_val(p1), node_val(p2)) {
                    (Some(v1), Some(v2)) => {
                        if v1 < v2 {
                            if (*node_next(pr)) != None && node_next(pr) == p2 {
                                l2 = (*node_next(pr)).take();
                                p2 = &mut l2 as *mut Option<Box<ListNode>>;                                
                            }                      
                            (*node_next(pr)) = (*p1).take();
                            pr = node_next(pr);
                            p1 = node_next(pr);
                        }else {
                            if (*node_next(pr)) != None && node_next(pr) == p1 {
                                l1 = (*node_next(pr)).take();
                                p1 = &mut l1 as *mut Option<Box<ListNode>>;                                
                            }                            
                            (*node_next(pr)) = (*p2).take();
                            pr = node_next(pr);                        
                            p2 = node_next(pr);
                        };            
                    },
                    (Some(_), None) => {
                        (*pr).as_mut().unwrap().next = (*p1).take();
                        break;
                    },
                    (None, Some(_)) => {
                        (*pr).as_mut().unwrap().next = (*p2).take();
                        break;
                    },
                    (None, None) => {
                        return None;
                    },
                }
            }
        }

        head.unwrap().next
    }
}

• 执行用时 : 0 ms, 在所有 Rust 提交中击败了100.00%的用户
• 内存消耗 : 1.9 MB, 在所有 Rust 提交中击败了83.33%的用户

总结

记忆：链表排序的最小时间复杂度为O(N*logN)，空间复杂度为O(1)。