合并两个有序链表

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

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

自我解答：
        这个就和归并排序的并一样，可以使用双指针解决

def merge_two_lists(l1: ListNode, l2: ListNode) -> ListNode:
    if not l1: return l2
    if not l2: return l1
    if l1.val <= l2.val:
        new_l3 = l1
        l1 = l1.next
    else:
        new_l3 = l2
        l2 = l2.next
    new_p = new_l3
    while l1 and l2:
        if l1.val <= l2.val:
            new_p.next = l1
            l1 = l1.next
        else:
            new_p.next = l2
            l2 = l2.next
        new_p = new_p.next
    new_p.next = l1 if l1 else l2
    return new_l3

力扣解答：
        还可以用递归的方式，一开始没想到。因为对比两个节点，能够找到更小的那个，但是如何能拿到上一个呢？
        在递归函数里明显是没有上一个。但是上一层递归里有，如果能把这层的较小值return到上一层递归中，
        就能解决了，这和”反转单链表“的递归思路一致，需要上层结点参与的操作，可以直接在上层处理，
        直接递归到最深处，自下而上处理。
        

def merge_two_lists_recursion(l1: ListNode, l2: ListNode) -> ListNode:
    if not l2: return l1
    if not l1: return l2
    if l1.val < l2.val:
        l1.next = merge_two_lists_recursion(l1.next, l2)
        return l1
    else:
        l2.next = merge_two_lists_recursion(l1, l2.next)
        return l2

原题链接：https://leetcode-cn.com/problems/merge-two-sorted-lists