Sort List

对于链表，时间复杂度O(nlgn)的算法只有归并排序比较好实现，快速排序非常复杂

class Solution(object):
    def sortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head:
            return None
        if not head.next:
            return head

        dummy = ListNode('d')
        dummy.next = head
        slow, fast = dummy, dummy
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        tmp = slow.next
        slow.next = None
        left = self.sortList(head)
        right = self.sortList(tmp)

        return self.merge(left, right)

    def merge(self, left, right):
        dummy = ListNode('d')
        cur = dummy
        while left and right:
            if left.val < right.val:
                cur.next = left
                left = left.next
            else:
                cur.next = right
                right = right.next
            cur = cur.next

        cur.next = left if left else right
        return dummy.next