C++链表插入排序代码
时间: 2024-08-13 14:05:59 浏览: 29
在C++中,链表不支持随机访问元素,因此不适合直接使用插入排序。但如果你坚持要在链表上实现插入排序,你可以遍历链表,对于每一个节点,将其值插入到已经排序的部分中的正确位置。以下是简单的插入排序链表的示例代码:
```cpp
#include <iostream>
// 链表节点定义
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
void insertionSortList(ListNode** head) {
ListNode* sorted = nullptr; // 已排序部分的头指针
ListNode* current = *head; // 当前待排序节点
while (current != nullptr) {
ListNode* nextToInsert = current->next; // 记录下一个待插入的节点
// 将当前节点插入已排序链表
if (sorted == nullptr || current->val <= sorted->val) {
current->next = sorted;
sorted = current;
} else {
ListNode* prev = sorted;
while (prev->next != nullptr && prev->next->val < current->val) {
prev = prev->next;
}
current->next = prev->next;
if (prev->next != nullptr) {
prev->next = current;
} else {
sorted = current;
}
}
current = nextToInsert; // 移动到下一个待排序的节点
}
*head = sorted; // 更新链表头指针
}
// 打印链表
void printList(ListNode* node) {
while (node != nullptr) {
std::cout << node->val << " -> ";
node = node->next;
}
std::cout << "nullptr" << std::endl;
}
int main() {
// 创建一个链表
ListNode* list = new ListNode(4);
list->next = new ListNode(2);
list->next->next = new ListNode(1);
list->next->next->next = new ListNode(3);
std::cout << "Before sorting: ";
printList(list);
insertionSortList(&list);
std::cout << "After sorting: ";
printList(list);
return 0;
}
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![txt](https://img-home.csdnimg.cn/images/20210720083642.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)