148. 排序链表(medium)

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
示例 1:
输入: 4->2->1->3
输出: 1->2->3->4
示例 2:
输入: -1->5->3->4->0
输出: -1->0->3->4->5

• show the code:

# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def sortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head or not head.next:
            return head
        pre,slow,quick = None,head,head
        while quick and quick.next:
            pre = slow
            slow = slow.next
            quick = quick.next.next
        pre.next = None
        return self.merge(*map(self.sortList,(head,slow)))
    def merge(self,l1,l2):
        if l1 and l2:
            if l1.val > l2.val:
                l1,l2 = l2,l1
            l1.next = self.merge(l1.next,l2)
        return l1 or l2

• 此题由于题目条件限制，采用归并排序。分为两个步骤：第一步将链表从中点截成两段，这一步可以使用快慢指针来解决。第二步递归的融合两个有序链表，这个在之前的题目中有涉及到：合并两个有序链表
• 其实此题也就是归并排序的思想，不断的分为两半，最后分到一个数的时候，链表一定是有序的，再递归回去，合并两个有序链表即可。