一、题目
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
