排序链表

项目场景：

提示：这里简述项目相关背景：

原因分析：

提示：这里填写问题的分析：

自顶向下归并排序 基本步骤： (1)找到链表的中点，以中点为分界，将链表拆分成两个子链表。寻找链表的中点可以使用快慢指针的做法，快指针每次移动 22 步，慢指针每次移动 11 步，当快指针到达链表末尾时，慢指针指向的链表节点即为链表的中点。

(2)对两个子链表分别排序

(3)将两个排序后的子链表合并，得到完整的排序后的链表

通过递归实现链表归并排序，有以下两个环节

1.分割 cut 环节： 找到当前链表中点，并从中点将链表断开（以便在下次递归 cut 时，链表片段拥有正确边界）；

(1)使用 fast,slow 快慢双指针法，奇数个节点找到中点，偶数个节点找到中心左边的节点

(2)找到中点 slow 后，执行 slow->next = None 将链表切断。

(3)递归分割时，输入当前链表左端点 head 和中心节点 slow 的下一个节点 tmpe(因为链表是从 slow 切断的)

(4)cut 递归终止条件： 当head.next == None时，说明只有一个节点了，直接返回此节点

2.合并 merge 环节： 将两个排序链表合并，转化为一个排序链表