文章目录
- 前言
- 摘要
- 问题描述
- 题解
- 解题思路
- Swift 实现代码
- 代码分析
- 示例测试与结果
- 时间复杂度
- 空间复杂度
- 总结
- 关于我们
前言
本题由于没有合适答案为以往遗留问题，最近有时间将以往遗留问题一一完善。
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)时间复杂度内完成排序：
- 分割链表：递归地将链表从中间分为两个子链表，直到每个子链表只有一个节点。
- 合并有序链表：将两个已排序的链表按照升序合并成一个新的有序链表。
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
}
代码分析
-
查找链表中点
- 使用快慢指针找到链表的中间节点并将链表分成两部分。
- 时间复杂度：
O(n) - 空间复杂度：
O(1)
-
递归排序
- 不断分割链表直到只有一个节点时停止递归，然后逐步合并已排序的链表。
-
合并有序链表
- 使用双指针遍历两个已排序链表，按值大小将节点逐个合并。
- 时间复杂度：
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 基础为核心的技术内容，也整理收集优秀的学习资料。
