给定一个带头节点的单链表设计算法,按递增次序输出单列表中各节点的数据元素,并释放节点所占的存储空间,要求不使用数组作为辅助空间。用C++写出代码
时间: 2024-10-28 21:09:04 浏览: 12
西南交通大学-zhy-数据结构第4次作业.docx
5星 · 资源好评率100%
要按递增次序输出单链表中各节点的数据元素,并释放节点所占的存储空间,可以使用归并排序的思想。归并排序是一种有效的排序算法,其时间复杂度为O(n log n),并且可以在原地进行排序,不需要额外的数组作为辅助空间。
下面是使用C++实现的代码:
```cpp
#include <iostream>
using namespace std;
// 定义单链表节点结构体
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
// 合并两个有序链表
ListNode* merge(ListNode* l1, ListNode* l2) {
ListNode dummy(0);
ListNode* tail = &dummy;
while (l1 && l2) {
if (l1->val < l2->val) {
tail->next = l1;
l1 = l1->next;
} else {
tail->next = l2;
l2 = l2->next;
}
tail = tail->next;
}
tail->next = l1 ? l1 : l2;
return dummy.next;
}
// 分割链表
void split(ListNode* head, ListNode** front, ListNode** back) {
ListNode* slow = head;
ListNode* fast = head->next;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
*front = head;
*back = slow->next;
slow->next = nullptr;
}
// 归并排序
ListNode* mergeSort(ListNode* head) {
if (!head || !head->next) return head;
ListNode* front = nullptr;
ListNode* back = nullptr;
split(head, &front, &back);
front = mergeSort(front);
back = mergeSort(back);
return merge(front, back);
}
// 打印链表并释放内存
void printAndFreeList(ListNode* head) {
while (head) {
cout << head->val << " ";
ListNode* temp = head;
head = head->next;
delete temp;
}
cout << endl;
}
int main() {
// 创建带头节点的单链表
ListNode* head = new ListNode(0); // 头节点不存储有效数据
ListNode* current = head;
int values[] = {4, 2, 5, 3, 1}; // 示例数据
for (int value : values) {
current->next = new ListNode(value);
current = current->next;
}
// 对链表进行归并排序
head->next = mergeSort(head->next);
// 打印排序后的链表并释放内存
printAndFreeList(head->next);
// 释放头节点
delete head;
return 0;
}
```
### 代码说明:
1. **ListNode结构体**:定义了单链表节点的结构体。
2. **merge函数**:合并两个有序链表。
3. **split函数**:将链表分成两半。
4. **mergeSort函数**:递归地对链表进行归并排序。
5. **printAndFreeList函数**:打印链表并释放每个节点的内存。
6. **main函数**:创建一个带头节点的单链表,插入一些示例数据,然后对其进行排序、打印并释放内存。
这个实现方法没有使用额外的数组作为辅助空间,完全在链表上进行操作,符合题目要求。
阅读全文