c++中如何实现链表排序_c++链表排序实现方法-C++-PHP中文网

c++中如何实现链表排序_c++链表排序实现方法

下次还敢

发布： 2025-09-27 16:46:01

原创

825人浏览过

归并排序是链表排序的首选方法，因其稳定的时间复杂度O(n log n)且适合链表结构。1. 自顶向下归并排序通过快慢指针划分链表，递归合并，代码清晰高效；2. 转换为数组排序利用std::sort，简单但需额外空间，不满足原地要求；3. 自底向上归并排序采用迭代方式，避免深度递归导致的栈溢出，适合长链表。推荐使用自顶向下归并排序，若担心栈深度则选用自底向上版本，数组法仅在空间不限时考虑。

c++中如何实现链表排序_c++链表排序实现方法

在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排序后再写回链表。

简篇AI排版

AI排版工具，上传图文素材，秒出专业效果！

554

查看详情

#include <vector> #include <algorithm>

void sortListArray(ListNode head) { std::vector vals; ListNode curr = head; while (curr) { vals.push_back(curr->val); curr = curr->next; }

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; }

基本上就这些。归并排序是最推荐的方式，尤其是自顶向下版本代码清晰，适合大多数场景。如果担心递归深度，可用自底向上版本。数组法虽然简单，但破坏了链表原地操作的优势。选择哪种方法取决于性能要求和空间限制。

以上就是c++++中如何实现链表排序_c++链表排序实现方法的详细内容，更多请关注php中文网其它相关文章！