题目

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

示例：

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

思路
参考链表

单链表相关知识，递归实现

Python实现

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if l1 == None:
            return l2
        if l2 == None:
            return l1
        result = ListNode(None)
        if l1.val >= l2.val:
            result = l2
            result.next = self.mergeTwoLists(l1,l2.next)
        else:
            result = l1
            result.next = self.mergeTwoLists(l1.next, l2)
            
        return result

Golang实现

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
	if l1 == nil {
		return  l2
	}
	if l2 == nil {
		return l1
	}
	var result *ListNode
	if l1.Val >= l2.Val {
		result = l2
		result.Next = mergeTwoLists(l1,l2.Next)
    } else {
        result = l1
		result.Next = mergeTwoLists(l1.Next,l2)
    }
	return result
}

JavaScript实现

var mergeTwoLists = function(l1, l2) {
    if (l1 == null) {
        return l2
    }
    if (l2 == null) {
        return l1
    }
    var result = ListNode(null);
    if (l1.val >= l2.val) {
        result = l2
        result.next = mergeTwoLists(l1,l2.next)
    } else {
        result = l1
        result.next = mergeTwoLists(l1.next,l2)
    }
    return result
};

Rust实现

impl Solution {
    pub fn merge_two_lists(l1: Option<Box<ListNode>>, l2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        let  l11 = l1.as_ref().unwrap();
        let  l22 = l2.as_ref().unwrap();
        if let Some(L1) = l1.as_ref() {
            println!("{:?}",L1);
        } else {
            return l2;
        }
        if let Some(L2) = l2.as_ref() {
            println!("{:?}",L2);
        } else {
            return l1;
        }
        let mut reslut = Box::new(ListNode::new(-1));

        if l11.val >= l22.val {
            reslut = l2.unwrap();
            let  res = reslut.as_ref();
            let mut  n = res.next;
            let b: Option<Box<ListNode>> = Solution::merge_two_lists(l1, l22.next);
             n = b;
        } else {
            reslut = l1.unwrap();
            let  res = reslut.as_ref();
            let mut  n = res.next;
            let b: Option<Box<ListNode>> = Solution::merge_two_lists(l11.next,l2);
            n = b;
        }
        return Some(reslut)
    }
}

结果

代码下载地址

代码下载地址 https://github.com/ai-word