大家好，我就是那个在B站讲算法的「华南溜达虎」。
据环球时报报道，日本东京都政府将允许其员工每周工作 4天，以扭转日本的低出生率。东京都政府的这一计划将于2025年4月启动。
评论区不少同学表示非常羡慕，期望自己所在的公司能够落实双休就可以。也有同学开玩笑说，他们一点也不勤劳，也不能吃苦，没前途，虽然他们工资比我们高，但是做事不能只看钱。
最近虎哥利用业余时间在B站讲算法，id「华南溜达虎」，我已经把算法面试高频题目列表blind75中的题目讲了一遍，力扣hot100也快讲完了，一个视频五分钟左右，利用空闲时间就把算法学会了，对跳槽找工作升职加薪甚至对考研都有帮助，感兴趣的同学可以 点击底部的「查看全文」 去学习一下。很多看过虎哥视频的同学都反馈讲的由浅及深，清晰明了，下面是一小部分评论截图。
言归正传，今天我们来分享一道高频面试原题「排序链表」。
题目描述
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
举个例子：
输入：head = [4,2,1,3]
输出：[1,2,3,4]
思路解析
比较简单的解法应该是利用一个数组，把链表的节点全部存到数组中，然后使用快排根据节点中的值的大小对数组排序，排序以后把数组中的节点重新串起来，这种方法的空间复杂度比较高，为 O(n)，我们可以使用归并排序的思想，来进一步降低空间复杂度。
使用递归的归并排序
使用递归形式的归并排序步骤如下：
把链表拆成两部分，两部分的节点总数最多相差一个。 分别对两部分进行归并排序。 对排序后的两部分有序链表进行合并。
整个归并的过程是对链表不断对半分割，直到分割成n个单独的节点，然后再两两合并，一直合并成一个有序链表的过程，如下图。
python代码
class Solution:
def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
# 边界条件
if not head or not head.next:
return head
# 找到链表的中间节点
slow, fast = head, head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# 链表的第二部分
second = slow.next
slow.next = None
# 链表的第一部分
first = head
# 对第一部分进行排序
first = self.sortList(first)
# 对第二部分进行排序
second = self.sortList(second)
# 合并两个有序链表
return self.mergeList(first, second)
# 合并两个有序链表
def mergeList(self, left: ListNode, right: ListNode) -> ListNode:
# 创建一个虚拟的头节点避免处理边界条件
dummy = ListNode(0)
tail = dummy
while left and right:
# 选取val较小的节点放到tail后面
if left.val < right.val:
tail.next = left
left = left.next
else:
tail.next = right
right = right.next
# 保证tail一直指向新链表的最后一个节点
tail = tail.next
# 把剩下的有序节点挂到tail后面
if left:
tail.next = left
else:
tail.next = right
return dummy.next
复杂度分析
时间复杂度： 需要对链表合并 logn 次，所以时间复杂度为O(nlogn)，其中n为链表的长度。
空间复杂度： 因为整个过程使用了递归，涉及到函数栈的使用，所以空间复杂度为O(logn)。
使用迭代的归并排序
针对上面对链表递归形式的归并排序，我们可以省去对链表对半分割的过程，直接使用迭代的方式完成上面的第二部分合并的过程，可以把空间复杂度降低到O(1)，这里的难点在于处理各种指针的指向。
这里我们可以使用四个指针，tail指向已合并部分的尾部，first指向按步长step切割后的第一个要合并链表的头部，second指向按步长step切割后的第二个要合并链表的头部，nxtPair指向下一对要合并链表的头部。
下图展示了合并步长step = 1的合并过程。
每合并完一轮step变成原来的两倍，直到整个链表有序。
python代码
class Solution:
def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
# 获取链表中元素的个数
listCnt = 0
cur = head
while cur:
listCnt += 1
cur = cur.next
dummy = ListNode(0, head)
step = 1
while step < listCnt:
tail = dummy
# 下一个需要合并的链表对
nxtPair = dummy.next
while nxtPair:
first = nxtPair
second = first
n = step
# second先走n-1步
while n > 1 and second:
second = second.next
n -= 1
# 把first和second两个链表分离开，second再走一步
if second:
temp = second.next
second.next = None
second = temp
n = step
nxtPair = second
# nxtPair先走n-1步
while n > 1 and nxtPair:
nxtPair = nxtPair.next
n -= 1
# 把second和nxtPair两个链表分离开，nxtPair再走一步
if nxtPair:
temp = nxtPair.next
nxtPair.next = None
nxtPair = temp
tail.next = self.mergeList(first, second)
# 移动到已合并链表的尾部
while tail.next:
tail = tail.next
step *= 2
return dummy.next
# 合并两个有序链表
def mergeList(self, left: ListNode, right: ListNode) -> ListNode:
# 创建一个虚拟的头节点避免处理边界条件
dummy = ListNode(0)
tail = dummy
while left and right:
# 选取val较小的节点放到tail后面
if left.val < right.val:
tail.next = left
left = left.next
else:
tail.next = right
right = right.next
# 保证tail一直指向新链表的最后一个节点
tail = tail.next
# 把剩下的有序节点挂到tail后面
if left:
tail.next = left
else:
tail.next = right
return dummy.next
复杂度分析
时间复杂度： 需要对链表合并 logn 次，所以时间复杂度为O(nlogn)，其中n为链表的长度。
空间复杂度： 因为整个实现过程使用了迭代的方式，所以空间复杂度为O(1)。
今天的分享就到这里，希望大家有所收获！
