来源：编程网事
大家好，我就是那个在B站讲算法的「华南溜达虎」。
据环球时报报道，日本东京都政府将允许其员工每周工作 4天，以扭转日本的低出生率。东京都政府的这一计划将于2025年4月启动。
评论区不少同学表示非常羡慕，期望自己所在的公司能够落实双休就可以。也有同学开玩笑说，他们一点也不勤劳，也不能吃苦，没前途，虽然他们工资比我们高，但是做事不能只看钱。
言归正传，今天我们来分享一道高频面试原题「排序链表」。
给你链表的头结点 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)。
今天的分享就到这里，希望大家有所收获！
特别声明：以上内容仅代表作者本人的观点或立场，不代表新浪财经头条的观点或立场。如因作品内容、版权或其他问题需要与新浪财经头条联系的，请于上述内容发布后的30天内进行。
