python3常规算法+递归算法

1使用循环

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

#
# 
# @param l1 ListNode类 
# @param l2 ListNode类 
# @return ListNode类
#
class Solution:
    def mergeTwoLists(self , l1 , l2 ):
       #分别判断两个链表是否为空
        if not l1:
            return l2
        if not l2:
            return l1

        #以下处理两个链表都不为空的情况，
        ret = l1 if l1.val<=l2.val else l2 #以较小的作为新链表的起使
        l=ret #新链表的游标

        #移动已加入新链表的l1或者l2链表，避免重复
        cur1=l1 if ret is l2 else l1.next
        cur2=l2 if ret is l1 else l2.next

        while cur1 or cur2:
            #取到各游标当前值，只会出现一个游标是空的情况，为空赋值另一个游标当前值加一，保证该值不会使用
            val1 = cur1.val if cur1 else cur2.val+1
            val2 = cur2.val if cur2 else cur1.val+1

            if val1<=val2:
                l.next = cur1
                l = l.next
                cur1 = cur1.next

            else:
                l.next = cur2
                l = l.next
                cur2 = cur2.next

        #链表最后需要指向空
        l.next = None
        return ret            

递归算法：比较当前链表的值，较小的取其子链表继续递归。
当有一个链表取到子链表为空时，说明已经比较完成，可以直接返回非空的链表，返回值赋给了l1.next或者l2.next，但无论如何，最终还是沿着递归链不断返回，最终返回的是新有序链表的表头。

class Solution:
    def mergeTwoLists(self , l1 , l2 ):
        #递归退出条件
        if not l1 or not l2:
            return l1 if l1 else l2

        if l1.val<=l2.val:
            l1.next=self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next=self.mergeTwoLists(l1, l2.next)
            return l2