给定链表的头结点 head 请将其按 升序 排列并返回 排序后的链表

可以使用归并排序的思想对链表进行排序。

具体的步骤如下：

1. 如果链表为空或者只有一个节点，那么已经是有序的，直接返回。
2. 使用快慢指针找到链表的中点，将链表一分为二。
3. 分别对左右两个链表进行递归排序。
4. 合并两个有序链表，得到最终的有序链表。

代码实现如下：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def mergeTwoLists(l1, l2):
    if not l1:
        return l2
    if not l2:
        return l1
    if l1.val < l2.val:
        l1.next = mergeTwoLists(l1.next, l2)
        return l1
    else:
        l2.next = mergeTwoLists(l1, l2.next)
        return l2

def sortList(head):
    if not head or not head.next:
        return head
    
    slow, fast = head, head.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    
    mid, slow.next = slow.next, None
    left = sortList(head)
    right = sortList(mid)
    
    return mergeTwoLists(left, right)

时间复杂度分析：

• 对链表进行归并排序的时间复杂度为 O(nlogn)，其中 n 是链表的长度。
• 空间复杂度为 O(logn)，即递归调用的栈空间