排序链表，一般来讲【归并排序是最合适的】
链表存在严格的前驱后继关系，不能够像数组那样通过index实现对任一元素的O(1)定位。因此，像快排这些基于下标的排序算法不适用于链表排序
根据链表前驱后继的特性，像冒泡、归并就很合适，因为它们本质上都是基于相邻关系实现排序的。链表归并的时间复杂度O(NlogN)，空间复杂度O(1)，认为是最合适的
leetcode148. 排序链表
# 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: ListNode) -> ListNode:
# 链表的排序，归并是最合理的
# 递归写法
# 返回值：归并排序后的链表头
# 出口：head is None or head.next is None
# 转移式：两个有序链表的归并过程
if not head or not head.next:
return head
# 快慢指针找中点
vir_node = ListNode()
vir_node.next = head
slow = fast = vir_node
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# 依据中点划分两条链表，并各自归并
head2 = slow.next
slow.next = None
head1 = vir_node.next
head1, head2 = self.sortList(head1), self.sortList(head2)
# 合并两个有序链表
pre = ListNode()
p = pre
while head1 and head2:
if head1.val <= head2.val:
p.next = head1
head1 = head1.next
else:
p.next = head2
head2 = head2.next
p = p.next
if head1:
p.next = head1
if head2:
p.next = head2
return pre.next
