题解 | #单链表的排序#

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

解题思路：链表、归并排序、子问题

1. 解题工具：

• 递归逻辑，求解子问题
• 链表等分算法
• 链表合并算法

2.递归处理过程，实现链表切分和有序表合并

• 终止条件和返回值

#其一：单个节点为切分终点，返回长度为一的链表
while head or head.next:
	return head #

其二：返回合并后的有序链表
return mergeSortList(left,right) #返回有序链表

• 单层逻辑

leftH,rightH = listHalfCut(head) # 将当前链表等分，封装函数
#左右两分片，分别继续切分
left = sortList(leftH)
right = sortList(rightH)