一、题目

Merge Two Sorted Lists

二、解题

两个有序链表的排序。

三、尝试与结果

class Solution(object):
    def mergeTwoLists(self, l1, l2):
        ret = ListNode(0)
        if l1 == None:
            return l2
        if l2 == None:
            return l1

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

        return ret

结果：AC

四、学习与记录

这个其实算是一个归并排序：

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

每次2路归并的时候，就是这题了，自己的思维老是限制在了两个链表里面，让两个链表互相修改next，而没有想过跳出来，用一个新的链表组成（跳出来之后就海阔天空了~），2分钟搞定。

class Solution(object):
    def mergeTwoLists(self, l1, l2):
        if l1 == None:
            return l2
        if l2 == None:
            return l1
        ret = ListNode(0)
        head = ret
        while l1 != None and l2 != None:
            if l1.val > l2.val:
                ret.next = l2
                l2 = l2.next
            else:
                ret.next = l1
                l1 = l1.next
            ret = ret.next

        if l1 == None:
            ret.next = l2

        if l2 == None:
            ret.next = l1

        return head.next

结果：AC