给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
解题思路
主要是归并排序，即分治思想，两个数组都有序了之后再双指针合并。这个过程当中，链表排序涉及到：
1、如何寻找到中点来二分：快慢指针找到终点，这个过程道中涉及链表的分治问题时的边界问题，需要考虑好head.next=tail是一个元素的边界而不是两个。
2、在一个元素返回递归时，需要注意要将其变为独立结点，即next应改为空，只有这样才不会在合并的过程中发生乱指的问题
这是一个综合了快慢指针，链表合并，归并问题的综合型问题
# 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 sortListNode(head, tail):
if not head:
return head
if head.next == tail:
head.next = None
return head
fast = slow = head
while fast != tail:
fast = fast.next
slow = slow.next
if fast != tail:
fast = fast.next
mid = slow
return merge(sortListNode(head, mid), sortListNode(mid, tail))
def merge(a, b):
res = ListNode()
temp, list1, list2 = res, a, b
while list1 and list2:
if list1.val < list2.val:
temp.next = list1
temp = temp.next
list1 = list1.next
else:
temp.next = list2
temp = temp.next
list2 = list2.next
temp.next = list1 if list1 else list2
return res.next
return sortListNode(head, None)
官方题解
官方题解中还给出了一种自顶向上的方法，这种方法可以使得其只需要常数级的空间复杂度，需要通过记录链表长度来实现。
class Solution:
def sortList(self, head: ListNode) -> ListNode:
def merge(head1: ListNode, head2: ListNode) -> ListNode:
dummyHead = ListNode(0)
temp, temp1, temp2 = dummyHead, head1, head2
while temp1 and temp2:
if temp1.val <= temp2.val:
temp.next = temp1
temp1 = temp1.next
else:
temp.next = temp2
temp2 = temp2.next
temp = temp.next
if temp1:
temp.next = temp1
elif temp2:
temp.next = temp2
return dummyHead.next
if not head:
return head
length = 0
node = head
while node:
length += 1
node = node.next
dummyHead = ListNode(0, head)
subLength = 1
while subLength < length:
prev, curr = dummyHead, dummyHead.next
while curr:
head1 = curr
for i in range(1, subLength):
if curr.next:
curr = curr.next
else:
break
head2 = curr.next
curr.next = None
curr = head2
for i in range(1, subLength):
if curr and curr.next:
curr = curr.next
else:
break
succ = None
if curr:
succ = curr.next
curr.next = None
merged = merge(head1, head2)
prev.next = merged
while prev.next:
prev = prev.next
curr = succ
subLength <<= 1
return dummyHead.next
Q&A
Q： 为什么head.next == tail是一个元素的情况，我感觉像是两个。代码是对的但是我没有理解
A： 举例说明
假设链表有三个节点 A -> B -> C：
初始调用：sortFunc(A, None)
快慢指针遍历找到中点，链表被分为两部分：A 和 B -> C
递归调用：sortFunc(A, A) 和 sortFunc(B, None)
分割链表到单个节点的过程：
对于 sortFunc(A, A)：
head 是 A，tail 也是 A
根据条件 if head.next == tail，实际上是 A.next == A，条件不成立，但由于链表只有一个元素，所以 head.next 被设为 None，返回 A
对于 sortFunc(B, None)：
head 是 B，tail 是 None
快慢指针找到中点，分割为 sortFunc(B, B) 和 sortFunc(C, None)
sortFunc(B, B) 返回 B，sortFunc(C, None) 返回 C
核心理解：
当 head.next == tail 时，说明从 head 到 tail 只有一个元素。此时，将 head.next 设为 None，并返回 head，相当于链表只包含 head 这个单一节点。
由于 tail 是函数中的虚拟边界，不包含在链表中，所以实际处理时，head.next == tail 代表的是只有一个节点。
总结
head.next == tail 的判断是为了处理链表分割到只剩一个元素的情况。
这种判断方式有效地确保递归基于链表的分割能够正确终止，并处理只有一个元素的子链表。
通过上述解释，相信你能够理解为什么 head.next == tail 实际上处理的是一个元素的情况，而不是两个元素。
Q： 嗯我现在理解了，那么为什么一个元素的时候需要把head.next 改为None呢？
A： 将 head.next 设置为 None 的主要原因是为了确保在递归过程中，每个单独的节点成为一个独立的链表节点。这有助于在归并两个子链表时避免不必要的连接，从而保证链表的正确排序。具体原因如下：
保证链表分割正确
在归并排序中，链表被不断地分割直到每个子链表只包含一个元素。如果不将 head.next 设置为 None，那么在分割后的子链表中，原链表的 next 连接仍然存在，这可能导致在后续的合并过程中出现错误的连接。
避免循环引用
如果不将 head.next 设置为 None，链表的节点可能会保持原来的连接状态。在递归调用返回时，如果节点之间存在原来的连接，可能会导致链表的某些部分形成循环引用，最终导致程序进入死循环。
简化合并过程
在合并两个有序链表时，假设每个子链表的头节点都是独立的，简化了合并过程。如果 head.next 没有设置为 None，在合并时需要处理更多的连接关系，增加了代码的复杂性和出错的可能性。
举例说明
假设链表为 A -> B -> C，在分割过程中：
初始调用：sortFunc(A, None)
分割为：sortFunc(A, A) 和 sortFunc(B, None)
在处理 sortFunc(A, A) 时，如果不将 head.next 设置为 None，A 仍然指向 B。
这样在后续的合并过程中，可能会错误地将 B 连接到 A 上，导致排序失败。
通过将 head.next 设置为 None，确保 A 成为独立的节点，没有任何连接，合并时只需要简单地比较和连接节点即可。