1. 概述
在本篇文章中，我们将探讨如何使用归并排序算法对链表进行排序。
归并排序是经典的分治算法，非常适合处理链表结构，因为链表的插入操作效率高，且不需要像数组那样频繁移动元素。
我们将介绍两种实现方式：
- 递归式归并排序
- 迭代式归并排序
最终我们会分析它们的性能和实现细节。
2. 问题定义
我们面对的问题是：给定一个链表，如何使用归并排序算法将其按升序排列？
链表结构中的每个节点包含两个字段：
data：节点存储的值next：指向下一个节点的指针
例如，原始链表如下所示：
排序后应变为：
3. 递归式归并排序
3.1. 核心思想
将链表从中间分成两个子链表，分别对两个子链表递归排序，最后将两个有序链表合并为一个有序链表。
3.2. 实现步骤
我们将整个过程分为三个函数：
getMiddle(head)：找到链表的中间节点merge(list1, list2)：合并两个有序链表mergeSort(head)：递归执行归并排序
3.3. 查找中间节点
public ListNode getMiddle(ListNode head) {
if (head == null) return head;
ListNode slow = head, fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
使用快慢指针技巧，快指针每次走两步，慢指针每次走一步。当快指针到链表末尾时，慢指针刚好在中间节点。
3.4. 合并两个有序链表
public ListNode merge(ListNode list1, ListNode list2) {
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
while (list1 != null && list2 != null) {
if (list1.val <= list2.val) {
tail.next = list1;
list1 = list1.next;
} else {
tail.next = list2;
list2 = list2.next;
}
tail = tail.next;
}
tail.next = (list1 != null) ? list1 : list2;
return dummy.next;
}
这个函数是归并排序的关键，它合并两个已排序的链表，返回合并后的头节点。
3.5. 归并排序主函数
public ListNode mergeSort(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode middle = getMiddle(head);
ListNode rightList = middle.next;
middle.next = null;
ListNode left = mergeSort(head);
ListNode right = mergeSort(rightList);
return merge(left, right);
}
✅ 注意：middle.next = null 是断开链表的重要操作，否则递归无法终止。
3.6. 时间与空间复杂度
- 时间复杂度：O(N log N)
- 空间复杂度：**O(log N)**（递归栈）
4. 迭代式归并排序
4.1. 核心思想
不使用递归，而是从最小单位（每个节点作为一个有序块）开始，逐步合并相邻的两个有序块，直到整个链表有序。
4.2. 实现步骤
我们仍然使用 merge 函数，但不再递归，而是通过循环控制块大小。
4.3. 合并两个块
private ListNode mergeBlocks(ListNode left, int leftSize, ListNode right, int rightSize) {
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
while (leftSize > 0 && rightSize > 0) {
if (left.val <= right.val) {
tail.next = left;
left = left.next;
leftSize--;
} else {
tail.next = right;
right = right.next;
rightSize--;
}
tail = tail.next;
}
tail.next = (leftSize > 0) ? left : right;
// 找到合并后的尾节点，用于下一次拼接
while (tail.next != null) {
tail = tail.next;
}
return dummy.next;
}
4.4. 迭代排序主函数
public ListNode iterativeMergeSort(ListNode head) {
if (head == null || head.next == null) return head;
int length = 0;
ListNode current = head;
while (current != null) {
length++;
current = current.next;
}
ListNode dummy = new ListNode(0, head);
for (int size = 1; size < length; size <<= 1) {
ListNode prev = dummy;
ListNode curr = dummy.next;
while (curr != null) {
int leftSize = Math.min(size, countRemaining(curr));
int rightSize = Math.min(size, countRemaining(curr.next));
ListNode left = curr;
curr = advance(curr, leftSize);
ListNode right = curr;
curr = advance(curr, rightSize);
ListNode merged = mergeBlocks(left, leftSize, right, rightSize);
prev.next = merged;
while (prev.next != null) {
prev = prev.next;
}
}
}
return dummy.next;
}
private int countRemaining(ListNode node) {
int count = 0;
while (node != null && count < size) {
count++;
node = node.next;
}
return count;
}
private ListNode advance(ListNode node, int steps) {
while (node != null && steps-- > 0) {
node = node.next;
}
return node;
}
⚠️ 说明：这部分代码较复杂，建议调试理解，核心在于控制每次合并的块大小。
4.5. 时间与空间复杂度
- 时间复杂度：O(N log N)
- 空间复杂度：**O(1)**（原地修改链表）
5. 总结
| 方法 | 时间复杂度 | 空间复杂度 | 是否稳定 | 是否原地 |
|---|---|---|---|---|
| 递归式归并排序 | O(N log N) | O(log N) | ✅ 是 | ❌ 否 |
| 迭代式归并排序 | O(N log N) | O(1) | ✅ 是 | ✅ 是 |
✅ 选择建议：
- 如果你追求简洁易懂，且不介意递归栈开销，优先使用递归式归并排序
- 如果你在处理非常大的链表，或受限于栈空间，使用迭代式归并排序
⚠️ 踩坑提醒：
- 合并前记得切断链表连接（
middle.next = null） - 合并时注意边界条件（空链表、奇数个节点）
- 迭代版本需要额外处理块大小和剩余节点数
归并排序是链表排序的首选算法之一，理解其实现细节对于掌握链表操作非常重要。希望本文能为你在面试或实际开发中提供帮助！