【LeetCode with Python】 Sort List

博客域名：http://www.xnerv.wang
原题页面：https://oj.leetcode.com/problems/sort-list/
题目类型：
难度评价：★
本文地址：http://blog.csdn.net/nerv3x3/article/details/38143633

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

class Solution:

    def findMiddle(self, head):
        slow = head
        fast = head.next
        while None != fast and None != fast.next:
            fast = fast.next.next
            slow = slow.next
        return slow

    def mergeList(self, head):
        if None == head.next:
            return head
        mid = self.findMiddle(head)
        right_head = mid.next
        mid.next = None
        left_list = self.mergeList(head)
        right_list = self.mergeList(right_head)
        new_head = ListNode(-1)
        new_tail = new_head
        left_node = left_list
        right_node = right_list
        while None != left_node and None != right_node:
            if left_node.val <= right_node.val:
                new_tail.next = left_node
                left_node = left_node.next
            else:
                new_tail.next = right_node
                right_node = right_node.next
            new_tail = new_tail.next
        new_tail.next = left_node if None != left_node else right_node
        return new_head.next

    # @param head, a ListNode
    # @return a ListNode
    def sortList(self, head):
        if None == head:            # leetcode will input this !
            return None
        return self.mergeList(head)