链表排序

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

---

插入排序法

和数组的方式类似，时间复杂度为O(n^2)
对应147. 对链表进行插入排序

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def insertionSortList(self, head: ListNode) -> ListNode:
        if not head:
            return head
        dummy = ListNode()
        dummy.next = head
        undo = head.next
        head.next = None
        while undo:
            cur = undo
            undo = undo.next
            p = dummy
            q = dummy.next
            # p,q之间即为带插入的节点的位置, cur为待插入的节点
            while q and q.val < cur.val:
                q = q.next
                p = p.next
            cur.next = q
            p.next = cur
        return dummy.next

归并排序

自顶向下递归

时间复杂度O(nlogn)
空间复杂度O(logn)

对链表自顶向下归并排序的过程如下。

找到链表的中点，以中点为分界，将链表拆分成两个子链表。寻找链表的中点可以使用快慢指针的做法，快指针每次移动 2 步，慢指针每次移动 1 步，当快指针到达链表末尾时，慢指针指向的链表节点即为链表的中点。
对两个子链表分别排序。

将两个排序后的子链表合并，得到完整的排序后的链表。可以使用「21. 合并两个有序链表」的做法，将两个有序的子链表进行合并。

上述过程可以通过递归实现。递归的终止条件是链表的节点个数小于或等于 11，即当链表为空或者链表只包含 11 个节点时，不需要对链表进行拆分和排序。

# 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]:
        def mergeTwoList(list1, list2):
            if not list1:
                return list2
            if not list2:
                return list1

            dummy = ListNode()
            p = dummy
            while list1 and list2:
                if list1.val < list2.val:
                    p.next = list1
                    list1 = list1.next
                else:
                    p.next = list2
                    list2 = list2.next
                p = p.next
            
            p.next = list1 if list1 else list2
            return dummy.next
        
        def helper(head, tail):
            if not head:
                return head
            if head.next == tail:
                head.next = None
                return head
            slow = head
            fast = head
            while fast != tail:
                slow = slow.next
                fast = fast.next
                if fast != tail:
                    fast = fast.next
            mid = slow
            return mergeTwoList(helper(head, mid), helper(mid, tail))
        
        return helper(head, None)
                    

自底向上归并

迭代法，写起来细节有点繁琐，留TODO