本文共 818 字，大约阅读时间需要 2 分钟。

Sort a linked list in O(n log n) time using constant space complexity.

思路：能够有O(n lgn)时间复杂度的算法为，快速排序，堆排序，归并排序，三者的空间复杂度分别为O(1), O(N),O(N) 其中归并排序，其的基本思路就是将数组分成二组A，B，如果这二组组内的数据都是有序的，那么就可以很方便的将这二组数据进行排序。如何让这二组组内数据有序了，可以将A，B组各自再分成二组。依次类推，当分出来的小组只有一个数据时，可以认为这个小组组内已经达到了有序，然后再合并相邻的二个小组就可以了。这样通过先递归的分解数列，再合并数列就完成了归并排序。 此题采用归并排序，因为链表的排序不需要像数组那样单独分配一个新数组空间。 结合109. Convert Sorted List to Binary Search Tree 和21. Merge Two Sorted Lists 109即一颗归并二叉树，21再将二叉树的结点合并即可 Runtime: 422 ms

# Definition for singly-linked list.# class ListNode(object):#     def __init__(self, x):#         self.val = x#         self.next = Noneclass Solution(object):    def  merge(self,l1,l2):        if not l1:            return l2        if not l2:            return  l1        dummy=ListNode(0)        p=dummy        while l1 and l2:            if l1.val

转载地址：http://odfin.baihongyu.com/