合并有序链表（python版）

跟合并有序数组差不多套路，就是数据结构麻烦些。
思路：
先选出第一个节点，然后遍历两个链表，把小的作为当前节点的下一个节点，一直到其中一个链表遍历完，这时候把另一个链表直接接上。

当然实现起来有递归和非递归版本，看你喜欢哪个啦，都没毛病，不过递归可能代码更短小精湛些。
代码1（非递归版）：

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

class Solution:
    def mergeTwoLists(self , l1 , l2 ):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        if not l1: return l2
        if not l2: return l1
        cur = dump = ListNode(0)
        while l1 and l2:
            if l1.val >= l2.val:
                cur.next = l2
                l2 = l2.next
                cur = cur.next
            else:
                cur.next = l1
                l1 = l1.next
                cur = cur.next
        cur.next = l1 if l1 else l2
        return  dump.next

代码2（递归版）：

class Solution:
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        if not l1: return l2
        if not l2: return l1
        if l1.val <= l2.val:
            ret = l1
            ret.next = self.mergeTwoLists(l1.next, l2)
        else:
            ret = l2
            ret.next = self.mergeTwoLists(l1, l2.next)
        return ret

麻豆出品，必出精品！