Leetcode Link: 148. 排序链表 - 力扣（LeetCode） (leetcode-cn.com)
题目
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
要求时间复杂度，额外空间复杂度
解法一
思路：自上向下的递归。即我们在归并排序中的递归策略，从顶部开始，不断向下递归，直到递归到底停止，再一点一点返回来。如何找到中点是本思路的重中之重。
但是，这种方法虽然时间复杂度为，其空间复杂度收到递归栈的影响，其递归栈的深度就是该算法的空间复杂度，为
Note
能够产生的额外空间复杂度就是因为一直再利用中点进行二分，其递归栈然后又有点类似树一样。
题解：
class Solution:
# 找链表的中点，直接用快慢指针！
def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
return self.mergeSort(head)
def mergeSort(self, lists):
if lists==None or lists.next==None:
return lists
else:
# 找中点，中点为slow
# 这里要思考，对于奇数偶数个节点，怎么找到他的中点，最后的那个None会有影响，最好画图想想。
fast = lists
slow = lists
while(fast.next!=None):
if fast.next.next!=None:
fast = fast.next.next
slow = slow.next
else:
fast = fast.next
# 获得右链表
l_right = slow.next
# 断开中点之后的节点，获得左链表
# 一定记得要断开，要不然就是全部的链表了。
slow.next = None
l_left = lists
leftList = self.mergeSort(l_left)
rightList = self.mergeSort(l_right)
mergeList = self.merge(leftList,rightList)
return mergeList
def merge(self, left, right):
dummy = ListNode()
cur = dummy
while(left!=None and right!=None):
if left.val < right.val:
cur.next = left
left = left.next
cur = cur.next
else:
cur.next = right
right = right.next
cur = cur.next
if left!=None:
cur.next = left
if right!=None:
cur.next = right
return dummy.next解法二
思路：自下而上的排序。时间复杂度，空间复杂度。
详细的题解可以参考：Sort List （归并排序链表）题解
题解：
class Solution:
def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
# 计算链表的长度
cur = head
N = 0
while(cur):
cur = cur.next
N += 1
# 自下向上开始排序并合并。
dummy = ListNode(-1, head)
cur = dummy.next
last_end = dummy
k = 1
while(k < N):
while(cur):
## 找左半部分的起点和终点
left = cur
for _ in range(0,k-1):
if cur.next:
cur = cur.next
else:
# 如果左部分都不全，那不可能有右边，直接接上就行（因为左右都已经排好序了）
# 把“接上”的代码写在了下面，是等价的，因为一定没有右边。
break
left_end = cur
## 找右半部分的起点
### 没有右半部分，说明也能直接接上左边。
if not cur.next:
last_end.next = left
break
else:
cur = cur.next
right = cur
for _ in range(0,k-1):
if cur.next:
cur = cur.next
else:
# 有右边就必须合并排序
break
right_end = cur
# cur 再走一步，为下一次循环做准备，然后就可以断开左右终点之后的节点了。
cur = cur.next # 前面都是判断的 cur.next, 所以cur.next一定有，最次是None
left_end.next = None
right_end.next = None
## 合并左右，并接上上一次的尾巴
last_end.next = self.mergeTwo(left, right)
### last_end移动到尾部(找到新的last_end)
while(last_end.next):
last_end = last_end.next
k *= 2
# 重置，很重要。
cur = dummy.next
last_end = dummy
return dummy.next
def mergeTwo(self, left, right):
dummy = ListNode()
cur = dummy
while(left and right):
if left.val < right.val:
cur.next = left
cur = cur.next
left = left.next
else:
cur.next = right
cur = cur.next
right = right.next
if left:
cur.next = left
if right:
cur.next = right
return dummy.next