def sortList(self, head):
        if not head or not head.next:
            return head

        dummy = ListNode(0)
        dummy.next = head

        slow_pre = dummy
        fast_pre = dummy
        while fast_pre.next and fast_pre.next.next:
            fast_pre = fast_pre.next.next
            slow_pre = slow_pre.next

        mid_head = slow_pre.next
        dummy_mid = ListNode(0)

        # sort sub-problem
        slow_pre.next = None  # break
        head = self.sortList(head)
        mid_head = self.sortList(mid_head)

        # then merge
        dummy.next = head
        dummy_mid.next = mid_head
        pre = dummy
        pre_mid = dummy_mid
        while pre.next and pre_mid.next:
            if pre.next.val > pre_mid.next.val:
                pre.next, pre_mid.next.next, pre_mid.next = pre_mid.next, pre.next, pre_mid.next.next
                pre = pre.next
            else:
                pre = pre.next

        # dangling
        if  pre_mid.next:
            pre.next = pre_mid.next

        return dummy.next
Quick sort: not guarantee to be O(n lgn)
dataset/ETHPy150Open algorhythms/LeetCode/148 Sort List.py/Solution.sortList