148. 排序链表

题目链接

解题思路：在链表上使用排序算法。注意，不能使用快排，因为快排的最差时间复杂度是O(n^2)，数组形式的快排，以随机数划分能够得到O(n*logn)，但是链表的形式，不太好以随机数的方式划分。所以最好的排序方法是使用归并排序。

• 先用快慢指针，将链表分成两部分，然后两部分分别归并排序，得到两个链表的头和尾。然后再merge即可

代码

class Solution:


    def process(self, node: Optional[ListNode]) -> (Optional[ListNode], Optional[ListNode]):
        slow = node
        if slow.next == None:
            return slow, slow
        fast = slow.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next
            if fast == None:
                break
            fast = fast.next
        # 分别有序
        tmp = slow.next
        slow.next = None
        head1, tail1 = self.process(node)
        head2, tail2 = self.process(tmp)
        # 合并
        ans_head  = None
        ans_tail = tail1 if tail1.val >= tail2.val else tail2
        if head1.val <= head2.val:
            ans_head = head1
            head1 = head1.next
        else:
            ans_head = head2
            head2 = head2.next
        cur = ans_head
        while head1 and head2:
            if head1.val <= head2.val:
                cur.next = head1
                head1 = head1.next
            else:
                cur.next = head2
                head2 = head2.next
            cur = cur.next
        if head1:
            cur.next = head1
        if head2:
            cur.next = head2

        return ans_head, ans_tail



    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head == None:
            return None
        head1, _ = self.process(head)
        return head1