题目如下：

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

Example 1:

Input: 4->2->1->3Output: 1->2->3->4

Example 2:

Input: -1->5->3->4->0Output: -1->0->3->4->5

解题思路：因为题目要求时间复杂度是O(nlogn)，所以快排应该是合适的方法。原理也和快速排序差不多，我的方法是引入五个指针，分别是small_head,small_tail,large_head,large_tail,equal_tail，首先对list进行遍历，以head.val作为基准，小于head.val的保存到small的list里面，用small_head,small_tail分别指向small list的头结点和尾节点；大于head.val的保存到large list里面，用large_head,large_tail分别指向 list的头结点和尾节点；等于head.val的存入equal list，复用现有的head结点，equal_tail指向equal的尾节点。分组完成后，再对small list和large list做递归，最后把small list的尾节点指向equal list的head，同时把equal list的尾节点指向large list的头结点即可。

代码如下：

# Definition for singly-linked list.# class ListNode(object):#     def __init__(self, x):#         self.val = x#         self.next = Noneclass Solution(object):    def quick(self,sublist_head):        if sublist_head == None:            return (None,None)        v = sublist_head.val        previous = sublist_head        current = sublist_head.next        little_head = None        little_current = None        large_head = None        large_current = None        equal_current = sublist_head        while current != None:            if current.val < v:                if little_head == None:                    little_current = current                    little_head = current                    current = current.next                    previous.next = current                    little_current.next = None                else:                    little_current.next = current                    little_current = little_current.next                    current = current.next                    previous.next = current                    little_current.next = None            elif current.val == v:                equal_current.next = current                previous = current                equal_current = equal_current.next                current = current.next            else:                if large_head == None:                    large_head = current                    large_current = current                    current = current.next                    previous.next = current                    large_current.next = None                else:                    large_current.next = current                    large_current = large_current.next                    current = current.next                    previous.next = current                    large_current.next = None        small_head,small_tail  =  self.quick(little_head)        big_head,big_tail  =  self.quick(large_head)        if small_head != None:            small_tail.next = sublist_head        equal_current.next = big_head        return (small_head if small_head != None else sublist_head,big_tail if big_tail != None else equal_current)    def sortList(self, head):        """        :type head: ListNode        :rtype: ListNode        """        return self.quick(head)[0]