归并排序是链表排序的首选方法，因其稳定的时间复杂度O(n log n)且适合链表结构。1. 自顶向下归并排序通过快慢指针划分链表，递归合并，代码清晰高效；2. 转换为数组排序利用std::sort，简单但需额外空间，不满足原地要求；3. 自底向上归并排序采用迭代方式，避免深度递归导致的栈溢出，适合长链表。推荐使用自顶向下归并排序，若担心栈深度则选用自底向上版本，数组法仅在空间不限时考虑。
在C++中对链表进行排序，常见方法包括转换为数组后排序再重建链表，或直接在链表上使用归并排序。由于链表不支持随机访问，快速排序效率不高，而归并排序更适合处理链表结构，时间复杂度稳定在O(n log n)。
1. 使用归并排序对链表排序
归并排序适合链表，因为可以通过快慢指针分割链表，递归合并有序部分。
// 定义链表节点 struct ListNode { int val; ListNode* next; ListNode(int x) : val(x), next(nullptr) {} };ListNode merge(ListNode l1, ListNode l2) { ListNode dummy(0); ListNode curr = &dummy;
while (l1 && l2) {
if (l1->val < l2->val) {
curr->next = l1;
l1 = l1->next;
} else {
curr->next = l2;
l2 = l2->next;
}
curr = curr->next;
}
curr->next = l1 ? l1 : l2;
return dummy.next;}
立即学习“C++免费学习笔记（深入）”；
ListNode sortList(ListNode head) { if (!head || !head->next) return head;
// 快慢指针找中点
ListNode *slow = head, *fast = head, *prev = nullptr;
while (fast && fast->next) {
prev = slow;
slow = slow->next;
fast = fast->next->next;
}
// 断开链表
prev->next = nullptr;
// 递归排序两部分
ListNode* left = sortList(head);
ListNode* right = sortList(slow);
// 合并
return merge(left, right);}
立即学习“C++免费学习笔记（深入）”；
2. 转换为数组排序（简单但占用额外空间）
将链表值存入vector，用std::sort排序后再写回链表。
#include
void sortListArray(ListNode head) {
std::vector
std::sort(vals.begin(), vals.end());
curr = head;
for (int v : vals) {
curr->val = v;
curr = curr->next;
}}
立即学习“C++免费学习笔记（深入）”；
3. 自底向上归并排序（避免递归栈溢出）
适用于长链表，通过迭代方式按子长度合并。
ListNode* sortListIterative(ListNode* head) { if (!head || !head->next) return head;// 获取链表长度
int len = 0;
ListNode* curr = head;
while (curr) {
len++;
curr = curr->next;
}
ListNode dummy(0);
dummy.next = head;
for (int subLen = 1; subLen < len; subLen <<= 1) {
ListNode* prev = &dummy;
ListNode* current = dummy.next;
while (current) {
ListNode* h1 = current;
ListNode* h2 = cut(h1, subLen);
current = cut(h2, subLen);
prev->next = merge(h1, h2);
while (prev->next) prev = prev->next;
}
}
return dummy.next;}
// 切断链表，返回后半部分头节点 ListNode cut(ListNode head, int n) { ListNode p = head; while (--n && p) { p = p->next; } if (!p) return nullptr; ListNode next = p->next; p->next = nullptr; return next; }
基本上就这些。归并排序是最推荐的方式，尤其是自顶向下版本代码清晰，适合大多数场景。如果担心递归深度，可用自底向上版本。数组法虽然简单，但破坏了链表原地操作的优势。选择哪种方法取决于性能要求和空间限制。
