题目描述：

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

题目大意：

使用常数空间复杂度，对一个链表执行O(n log n）时间复杂度的排序

解题思路：

归并排序，链表的中点可以通过“快慢指针”法求得。

Python代码：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # @param head, a ListNode
    # @return a ListNode
    def sortList(self, head):
        if head is None or head.next is None:
            return head
        mid = self.getMiddle(head)
        rHead = mid.next
        mid.next = None
        return self.merge(self.sortList(head), self.sortList(rHead))

    def merge(self, lHead, rHead):
        dummyNode = ListNode(0)
        dummyHead = dummyNode
        while lHead and rHead:
            if lHead.val < rHead.val:
                dummyHead.next = lHead
                lHead = lHead.next
            else:
                dummyHead.next = rHead
                rHead = rHead.next
            dummyHead = dummyHead.next
        if lHead:
            dummyHead.next = lHead
        elif rHead:
            dummyHead.next = rHead
        return dummyNode.next

    def getMiddle(self, head):
        if head is None:
            return head
        slow = head
        fast = head
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next
        return slow

 

本文链接：http://bookshadow.com/weblog/2014/11/21/leetcode-sort-list/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码