一、題目

Merge Two Sorted Lists

二、解題

兩個(gè)有序鏈表的排序。

三、嘗試與結(jié)果

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

結(jié)果：AC

四、學(xué)習(xí)與記錄

這個(gè)其實(shí)算是一個(gè)歸并排序：

歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個(gè)子序列有序，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表，稱為二路歸并。

每次2路歸并的時(shí)候，就是這題了，自己的思維老是限制在了兩個(gè)鏈表里面，讓兩個(gè)鏈表互相修改next，而沒有想過跳出來，用一個(gè)新的鏈表組成（跳出來之后就海闊天空了~），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

結(jié)果：AC