排序链表

1、题目

图1

2、题解

归并排序（递归法）

当输入\(head.next ==None\)时，直接返回None

该方法有两个环节：

分割（快慢指针）：找到当前链表中点，并从中点将链表断开。当\(head.next ==None\)时，说明只剩一个节点，直接返回该节点。

合并：将两个有序链表合并成一个有序列表。利用双指针进行合并：设立哨兵节点h作为头部，left，right分别指向两个链表头部，比较指针处节点值大小，从小到大加入合并链表头部，两指针交替进行，直到链表添加完成，返回哨兵节点的下个节点。

图2

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        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, right = self.sortList(head), self.sortList(mid)
        h = res=ListNode(0)
        while left and right:
            if left.val <= right.val: h.next,left = left, left.next
            else: h.next, right = right, right.next
            h = h.next
        
        h.next = left if left else right

        return res.next

归并排序（自底向上）还没看懂

未完待续