1
2

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

// @lc code=start
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
//    pub val: i32,
//    pub next: Option<Box<ListNode>>,
// }
//impl ListNode {
 //   #[inline]
 //  fn new(val: i32) -> Self {
 //       ListNode {
//            next: None,
//            val
//        }
//    }
//}
impl Solution {
    /// ## 解题思路
    /// - 递归
    /// 1 同时递归遍历两个链表；
    /// 2 遍历时, 比较两个链表结点值;
    ///   - 如果两个节点都为空，则为空；
    ///   - 如果有一个为空，则返回非空节点；
    ///   - 如果都不为空，则将小的节点取下，将剩下的和另一条链表递归合并；
    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)
                }
            }
        }
    }
}
// @lc code=end

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class ListNode:
    def __init__(self, x):ss
        self.val = x
        self.next = None

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        dummyNode = p = ListNode(0)
        while l1 and l2:
            if l1.val < l2.val:
                p.next = l1
                l1 = l1.next
            else:
                p.next = l2
                l2 = l2.next
            p = p.next
        while l1:
            p.next = l1
            l1 = l1.next
            p = p.next
        while l2:
            p.next = l2
            l2 = l2.next
            p = p.next
        return dummyNode.next