21. Merge Two Sorted Lists Easy

1/**
2 * [21] Merge Two Sorted Lists
3 *
4 * You are given the heads of two sorted linked lists list1 and list2.
5 * Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.
6 * Return the head of the merged linked list.
7 *  
8 * Example 1:
9 * <img alt="" src="https://assets.leetcode.com/uploads/2020/10/03/merge_ex1.jpg" style="width: 662px; height: 302px;" />
10 * Input: list1 = [1,2,4], list2 = [1,3,4]
11 * Output: [1,1,2,3,4,4]
12 * 
13 * Example 2:
14 * 
15 * Input: list1 = [], list2 = []
16 * Output: []
17 * 
18 * Example 3:
19 * 
20 * Input: list1 = [], list2 = [0]
21 * Output: [0]
22 * 
23 *  
24 * Constraints:
25 * 
26 * The number of nodes in both lists is in the range [0, 50].
27 * -100 <= Node.val <= 100
28 * Both list1 and list2 are sorted in non-decreasing order.
29 * 
30 */
31pub struct Solution {}
32#[allow(unused_imports)]
33use crate::util::linked_list::{ListNode, to_list};
34
35// problem: https://leetcode.com/problems/merge-two-sorted-lists/
36// discuss: https://leetcode.com/problems/merge-two-sorted-lists/discuss/?currentPage=1&orderBy=most_votes&query=
37
38// submission codes start here
39
40// Definition for singly-linked list.
41// #[derive(PartialEq, Eq, Clone, Debug)]
42// pub struct ListNode {
43//   pub val: i32,
44//   pub next: Option<Box<ListNode>>
45// }
46// 
47// impl ListNode {
48//   #[inline]
49//   fn new(val: i32) -> Self {
50//     ListNode {
51//       next: None,
52//       val
53//     }
54//   }
55// }
56impl Solution {
57    pub fn merge_two_lists(list1: Option<Box<ListNode>>, list2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
58        if let None = list1 {
59            return list2;
60        } else if let None = list2 {
61            return list1;
62        }
63        
64        let mut dummy = Some(Box::new(ListNode{val: 0, next:None}));
65
66        let mut l1 = &list1;
67        let mut l2 = &list2;
68        let mut current_cur = dummy.as_mut().unwrap();
69
70        while l1.is_some() || l2.is_some() {
71            if l1.is_none() {
72                if let Some(x) = l2 {
73                    current_cur.next = Some(Box::new(ListNode{val: x.val, next: None}));
74                    l2 = &l2.as_ref().unwrap().next;
75                }
76            } else if l2.is_none() {
77                if let Some(x) = l1 {
78                    current_cur.next = Some(Box::new(ListNode{val: x.val, next: None}));
79                    l1 = &l1.as_ref().unwrap().next;
80                }
81            } else {
82                let l1v = match l1 {
83                    Some(x) => x.val,
84                    None => i32::MAX,
85                };
86                let l2v = match l2 {
87                    Some(x) => x.val,
88                    None => i32::MAX,
89                };
90
91                if l1v > l2v {
92                    current_cur.next = Some(Box::new(ListNode{val: l2v, next: None}));
93                    l2 = &l2.as_ref().unwrap().next;
94                } else {
95                    current_cur.next = Some(Box::new(ListNode{val: l1v, next: None}));
96                    l1 = &l1.as_ref().unwrap().next;
97                }
98            }
99            current_cur = current_cur.next.as_mut().unwrap()
100        }
101        dummy.unwrap().next
102    }
103}
104
105// submission codes end
106
107#[cfg(test)]
108mod tests {
109    use super::*;
110    use crate::linked;
111
112    #[test]
113    fn test_21() {
114        let x = Solution::merge_two_lists(linked!(1,2,5), linked!(3,4));
115        ListNode::print(x.as_ref().unwrap());
116    }
117
118    #[test]
119    fn test_21_2() {
120        let x = Solution::merge_two_lists(linked!(1,2,4), linked!(3,5));
121        ListNode::print(x.as_ref().unwrap());
122    }
123
124    #[test]
125    fn test_21_3() {
126        let x = Solution::merge_two_lists(linked!(), linked!(1,2,3,4,5));
127        ListNode::print(x.as_ref().unwrap());
128    }
129}
130