链表排序的基本概念
链表排序是算法学习中的经典问题,与数组排序相比，链表由于不支持随机访问，排序策略需要特别设计，在Java中，链表通常通过ListNode类实现，每个节点包含val（值）和next（指向下一节点的指针），排序的目标是通过调整节点间的指针关系，使链表中的节点值按非降序或非升序排列，常见的排序方法包括归并排序、快速排序、插入排序等，其中归并排序因时间复杂度稳定且适合链表结构而被广泛采用。
归并排序：链表排序的高效方案
归并排序（Merge Sort）是链表排序的首选方法，其时间复杂度为O(n log n)，空间复杂度为O(1)（若采用迭代实现）或O(log n)（递归栈空间），归并排序的核心思想是“分治”，即通过递归将链表拆分为子链表，排序后再合并。
递归实现步骤
- 分割链表：使用快慢指针法找到链表中间节点，将链表分为前半部分和后半部分，快指针每次走两步，慢指针每次走一步，当快指针到达末尾时，慢指针的下一个节点即为中间节点，通过
slow.next = null切断链表。 - 递归排序：对前半部分和后半部分分别递归调用归并排序。
- 合并有序链表：双指针法合并两个有序链表，比较两个链表的头节点，将较小的节点接入结果链表，直至其中一个链表为空，再将剩余链表直接连接。
代码示例
class ListNode {
int val;
ListNode next;
ListNode(int val) { this.val = val; }
}
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) return head; // 终止条件：空链表或单节点链表
// 快慢指针找中点
ListNode slow = head, fast = head.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode mid = slow.next;
slow.next = null; // 切断链表
// 递归排序左右半部分
ListNode left = sortList(head);
ListNode right = sortList(mid);
// 合并有序链表
return merge(left, right);
}
private ListNode merge(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0); // 虚拟头节点简化合并逻辑
ListNode cur = dummy;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
cur.next = l1;
l1 = l1.next;
} else {
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
cur.next = l1 != null ? l1 : l2; // 连接剩余节点
return dummy.next;
}
插入排序：简单但效率较低的方案
插入排序（Insertion Sort）适用于小规模数据或基本有序的链表，其时间复杂度为O(n²)，空间复杂度为O(1)，核心思想是维护一个有序子链表，依次将未排序的节点插入到合适位置。
实现步骤
- 初始化一个虚拟头节点
dummy，用于连接已排序部分的头节点。 - 遍历原链表,每次取出一个节点
cur，在已排序子链表中从dummy.next开始遍历，找到cur的插入位置。 - 调整指针关系,将
cur插入到已排序子链表中。
代码示例
public ListNode insertionSortList(ListNode head) {
if (head == null) return null;
ListNode dummy = new ListNode(0); // 虚拟头节点
ListNode cur = head; // 待插入节点
while (cur != null) {
ListNode next = cur.next; // 保存下一个待插入节点
ListNode pre = dummy; // 从已排序部分头节点开始找插入位置
while (pre.next != null && pre.next.val < cur.val) {
pre = pre.next;
}
cur.next = pre.next; // 插入到pre之后
pre.next = cur;
cur = next; // 处理下一个节点
}
return dummy.next;
}
快速排序：理论高效但实现复杂
快速排序（Quick Sort）的平均时间复杂度为O(n log n)，但最坏情况下（如链表已有序）会退化为O(n²)，由于链表不支持随机访问，快速排序的分区操作需要额外空间，空间复杂度为O(log n)（递归栈）。
实现步骤
- 选择基准节点（通常选择头节点或随机节点）。
- 分区：将链表分为小于基准、等于基准、大于基准的三部分。
- 递归排序小于基准和大于基准的部分,最后将三部分连接起来。
代码示例
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) return head;
// 选择基准节点（此处选择头节点）
ListNode pivot = head;
ListNode leftDummy = new ListNode(0), left = leftDummy; // 小于基准的链表
ListNode rightDummy = new ListNode(0), right = rightDummy; // 大于基准的链表
ListNode equalDummy = new ListNode(0), equal = equalDummy; // 等于基准的链表
ListNode cur = head.next;
while (cur != null) {
if (cur.val < pivot.val) {
left.next = cur;
left = left.next;
} else if (cur.val > pivot.val) {
right.next = cur;
right = right.next;
} else {
equal.next = cur;
equal = equal.next;
}
cur = cur.next;
}
// 递归排序左右部分，并连接
left.next = null; right.next = null; equal.next = null;
ListNode sortedLeft = sortList(leftDummy.next);
ListNode sortedRight = sortList(rightDummy.next);
// 合并三部分
return connect(connect(sortedLeft, equalDummy.next), pivot, sortedRight);
}
private ListNode connect(ListNode left, ListNode mid, ListNode right) {
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
cur.next = left;
while (cur.next != null) cur = cur.next;
cur.next = mid;
while (cur.next != null) cur = cur.next;
cur.next = right;
return dummy.next;
}
排序方法的性能对比
| 排序方法 | 时间复杂度（平均） | 时间复杂度（最坏） | 空间复杂度 | 适用场景 |
|---|---|---|---|---|
| 归并排序 | O(n log n) | O(n log n) | O(log n) | 大规模数据，稳定排序 |
| 插入排序 | O(n²) | O(n²) | O(1) | 小规模数据或基本有序链表 |
| 快速排序 | O(n log n) | O(n²) | O(log n) | 平均性能优异，但需避免最坏情况 |
在Java中实现链表排序时,归并排序因稳定的时间复杂度和对链表结构的适配性成为最优解，递归实现的归并排序代码简洁，而迭代实现可进一步优化空间复杂度，插入排序虽然简单，但仅适用于小规模数据；快速排序在理论上有优势，但实际实现中需注意基准选择和分区操作，根据具体需求（如数据规模、是否允许额外空间）选择合适的排序方法，是解决链表排序问题的关键。
