2020/2/17

题目描述

• 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

相关标签

链表

解题思路

• 递归法
  算法：
  特殊的，如果 l1 或者 l2 一开始就是 null ，那么没有任何操作需要合并，所以我们只需要返回非空链表。否则，我们要判断 l1 和 l2 哪一个的头元素更小，然后递归地决定下一个添加到结果里的值。如果两个链表都是空的，那么过程终止，所以递归过程最终一定会终止。
  复杂度分析：
  时间复杂度：O(n+m)，递归过程中会遍历两个链表中的所有元素，所以时间复杂度与合并后的链表长度呈线性关系
  空间复杂度：O(n+m)，由于采用递归，需要 n + m 次函数调用，消耗掉 O(n+m)的空间。

• 迭代法
  算法
  采用迭代的前提条件是 l1 的首个节点小于 l2 的首个节点。
  依次判断 l2 的值是否处于 l1 的两个节点之间，如果是便插入该 l2 节点， 每次迭代 l1 的指针右移一位。当l1到尾部之后，直接将 l2 剩余的部分接在 l1 后面。
  复杂度分析
  时间复杂度：O(n+m)，遍历总次数大致为 n+m 次，每次迭代的时间为常数级。
  空间复杂度：O(1)。迭代的过程中只会需要几个指针的常数级别的空间。

源代码

递归法

    // 递归法
    pub fn merge_two_lists(l1: Option<Box<ListNode>>, l2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        match (l1, l2) {
            (None, None) => None,
            (None, r) => r,
            (l, None) => l,
            (Some(mut l), Some(mut r)) => {
                if l.val <= r.val {
                    l.next = Self::merge_two_lists(l.next, Some(r));
                    Some(l)
                } else {
                    r.next = Self::merge_two_lists(Some(l), r.next);
                    Some(r)
                }
            }
        }
    }

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

迭代法

    //迭代法
   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%的用户

总结

迭代法相比递归法可以省去一些空间，但是代码量会大上不少。链表相关的操作，尤其是要用到双指针的时候，可以考虑使用unsafe，能省去不少事情。option的take()方法也尤其重要。