leetcode [148] 排序链表

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

示例 1:

输入: 4->2->1->3
输出: 1->2->3->4

示例 2:

输入: -1->5->3->4->0
输出: -1->0->3->4->5

归并排序，链表拆成两段，递归排序。

class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        count = 0
        head_ = head
        while head_:
            count += 1
            head_ = head_.next
        if count < 2:
            return head
        return self.sortListCore(head, count)

    def sortListCore(self, head, n):
        if n < 2:
            return head
        if n == 2:
            minval, maxval = min(head.val, head.next.val), max(head.val, head.next.val)
            head.val, head.next.val = minval, maxval
            return head

        k = n // 2
        k_ = k - 1
        head_ = head
        while k_:
            head_ = head_.next
            k_ -= 1
        head2 = head_.next
        head_.next = None
        head1 = self.sortListCore(head, k)
        head2 = self.sortListCore(head2, n - k)
        head = ListNode(0)
        head_ = head
        while head1 and head2:
            if head1.val >= head2.val:
                head_.next = head2
                head2 = head2.next
            else:
                head_.next = head1
                head1 = head1.next
            head_ = head_.next
        head_.next = head1 if head1 is not None else head2
        return head.next

来自题解归并排序：

注意fast和slow的起始点要分开，防止出现两个节点无法递归成子区间的情况（函数内容第二行）

class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        if not head or not head.next: return head
        slow, fast = head, head.next
        while fast and fast.next:
            slow, fast = slow.next, fast.next.next
        mid, slow.next = slow.next, None
        left, right = self.sortList(head), self.sortList(mid)
        newhead = res = ListNode(0)
        while left and right:
            if left.val < right.val:
                newhead.next, left = left, left.next
            else:
                newhead.next, right = right, right.next
            newhead = newhead.next
        newhead.next = left if left else right

        return res.next