前言

本题由于没有合适答案为以往遗留问题，最近有时间将以往遗留问题一一完善。

148. 排序链表

不积跬步，无以至千里；不积小流，无以成江海，Swift社区 伴你前行。如果大家有建议和意见欢迎在文末留言，我们会尽力满足大家的需求。

难度水平：中等

摘要

如何高效地对链表进行升序排序一直是算法中的经典问题之一。本文将深入解析如何使用Swift语言实现基于归并排序的链表排序算法，满足O(n log n)的时间复杂度和常数级空间复杂度的需求。同时，提供一段可运行的代码模块，帮助读者快速理解和实战。

问题描述

给定一个单链表的头结点head，要求对链表节点按升序排序并返回排序后的链表。

示例输入与输出

• 示例 1：
  输入：head = [4, 2, 1, 3]
  输出：[1, 2, 3, 4]

• 示例 2：
  输入：head = [-1, 5, 3, 4, 0]
  输出：[-1, 0, 3, 4, 5]

• 示例 3：
  输入：head = []
  输出：[]

约束条件

• 链表中的节点数范围：[0, 5 * 10^4]
• 节点值范围：[-10^5, 10^5]

进阶要求

在O(n log n)时间复杂度和常数级空间复杂度下完成链表排序。

题解

解题思路

归并排序是链表排序的理想选择，因其适合链表的顺序特性，并能够在O(n log n)时间复杂度内完成排序：

1. 分割链表：递归地将链表从中间分为两个子链表，直到每个子链表只有一个节点。
2. 合并有序链表：将两个已排序的链表按照升序合并成一个新的有序链表。

Swift 实现代码

class ListNode {var val: Intvar next: ListNode?init(_ val: Int) {self.val = valself.next = nil}
}func sortList(_ head: ListNode?) -> ListNode? {// 基本情况：空链表或只有一个节点guard let head = head, head.next != nil else {return head}// 使用快慢指针找到链表中点let mid = findMiddle(head)let rightHead = mid.nextmid.next = nil// 递归对两部分排序let left = sortList(head)let right = sortList(rightHead)// 合并排序后的两部分return merge(left, right)
}func findMiddle(_ head: ListNode) -> ListNode {var slow = headvar fast = headwhile fast.next != nil, fast.next?.next != nil {slow = slow.next!fast = fast.next!.next!}return slow
}func merge(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {let dummy = ListNode(0)var current = dummyvar l1 = l1var l2 = l2while let node1 = l1, let node2 = l2 {if node1.val < node2.val {current.next = node1l1 = node1.next} else {current.next = node2l2 = node2.next}current = current.next!}current.next = l1 ?? l2return dummy.next
}

代码分析

1. 查找链表中点

   • 使用快慢指针找到链表的中间节点并将链表分成两部分。
   • 时间复杂度：O(n)
   • 空间复杂度：O(1)

2. 递归排序

   • 不断分割链表直到只有一个节点时停止递归，然后逐步合并已排序的链表。

3. 合并有序链表

   • 使用双指针遍历两个已排序链表，按值大小将节点逐个合并。
   • 时间复杂度：O(n)
   • 空间复杂度：O(1)

示例测试与结果

测试代码

func printList(_ head: ListNode?) {var current = headvar result: [Int] = []while let node = current {result.append(node.val)current = node.next}print(result)
}// 创建示例链表：[4, 2, 1, 3]
let head = ListNode(4)
head.next = ListNode(2)
head.next?.next = ListNode(1)
head.next?.next?.next = ListNode(3)// 调用排序函数
let sortedHead = sortList(head)// 打印结果
printList(sortedHead) // 输出：[1, 2, 3, 4]

测试结果

• 输入：[4, 2, 1, 3]
  输出：[1, 2, 3, 4]
• 输入：[-1, 5, 3, 4, 0]
  输出：[-1, 0, 3, 4, 5]
• 输入：[]
  输出：[]

时间复杂度

• 分割链表：每次递归调用的时间为O(n)，最多递归log n次，总复杂度为O(n log n)。
• 合并链表：每层递归的合并操作处理所有节点，总复杂度为O(n)。

总时间复杂度：O(n log n)。

空间复杂度

• 除递归调用外无需额外的存储空间，递归栈空间为O(log n)。

总空间复杂度：O(log n)。

总结

本文展示了如何在Swift中使用归并排序对链表进行高效排序，从分割链表到合并排序，算法步骤清晰，代码简洁。无论是处理小型链表还是大型数据集，该方法都能够在O(n log n)的时间内完成排序，是面试和实际开发中的理想解决方案。

关于我们

我们是由 Swift 爱好者共同维护，我们会分享以 Swift 实战、SwiftUI、Swift 基础为核心的技术内容，也整理收集优秀的学习资料。