一、题目描述

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

二、迭代法求解

1、解题思路

对于链表的问题求解，是需要画图的，大家可以自己在纸上画一画。迭代法的主要思路：创建一个空的头结点res用来存放结果。然后l1和l2两条链的数值进行比较，大的直接链接到ans.next上。剩下的依次比较和挪动指针就可以实现了。

2、具体代码

 def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        res = ListNode()
        ans = res
        while (l1 != None and l2 != None):
            if l1.val < l2.val:
                ans.next = l1
                ans = ans.next
                l1 = l1.next
            else:
                ans.next = l2
                ans = ans.next
                l2 = l2.next
        if l1 == None:
            ans.next = l2
        if l2 == None:
            ans.next = l1
        return res.next

三、递归求解

1、解题思路

另一种解题思路就是利用递归了，递归确实很简单，但是理解起来很费劲。简单说就是自己调用自己，先从第一个数调用到最后一个数（此时结果是层层函数调用的形式），接着从最后一层的具体数值往前推导就可以推出整个结果链表了。

2、具体代码

 while (l1 is not None and l2 is not None):
            if l1.val < l2.val:
                l1.next = self.mergeTwoLists(l1.next,l2)
                return l1
            else:
                l2.next = self.mergeTwoLists(l1,l2.next)
                return l2
        if l1 is None:
            return l2
        if l2 is None:
            return l1