用C++写单链表的排序
时间: 2024-09-29 07:04:28 浏览: 7
在C++中,可以使用多种算法对单链表进行排序,这里以插入排序为例,因为它的原理简单直观,适合处理小规模数据或者部分有序的数据:
```cpp
#include <iostream>
// 定义链表节点结构体
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
// 插入排序链表函数
ListNode* insertionSortList(ListNode* head) {
if (!head || !head->next) {
return head; // 空链表或只有一个元素,直接返回
}
ListNode dummy(0); // 创建虚拟头节点
dummy.next = head;
ListNode* curr = head;
while (curr->next != nullptr) {
ListNode* temp = curr->next; // 暂存下一个节点
// 将temp插入到已排序的部分的正确位置
while (dummy.next != curr && dummy.next->val < temp->val) {
dummy = dummy.next;
}
// 更新链接
temp->next = dummy.next;
dummy.next = temp;
curr = curr->next;
}
return dummy.next; // 返回排序后的链表头
}
// 打印链表
void printList(ListNode* head) {
ListNode* curr = head;
while (curr) {
std::cout << curr->val << " -> ";
curr = curr->next;
}
std::cout << "nullptr" << std::endl;
}
int main() {
// 创建链表并填充示例数据
ListNode* list = new ListNode{5};
list->next = new ListNode{2};
list->next->next = new ListNode{4};
list->next->next->next = new ListNode{1};
list->next->next->next->next = new ListNode{3};
std::cout << "Original List: ";
printList(list);
list = insertionSortList(list);
std::cout << "Sorted List: ";
printList(list);
delete list;
return 0;
}
```