用c++实现定义单链表的类,实现一个带头结点的单链表的逆置,并将逆置前后的单链表分别遍历输出。单链表中各结点的值和结点个数等自定。
时间: 2024-10-10 08:10:44 浏览: 36
在C++中,我们可以定义一个单链表类`ListNode`,包含一个整数值和指向下一个节点的指针。然后创建一个`SingleLinkedList`类,用于维护链表的基本操作,包括添加元素、删除元素以及逆置链表。以下是简单的实现:
```cpp
#include <iostream>
// 定义链表节点
class ListNode {
public:
int val; // 节点值
ListNode* next; // 指向下一个节点的指针
ListNode(int x) : val(x), next(nullptr) {} // 构造函数
};
// 单链表类
class SingleLinkedList {
private:
ListNode* head; // 头节点指针
public:
SingleLinkedList() : head(nullptr) {}
// 添加元素到链表末尾
void addNode(int value) {
ListNode* newNode = new ListNode(value);
if (!head) {
head = newNode;
} else {
ListNode* current = head;
while (current->next) {
current = current->next;
}
current->next = newNode;
}
}
// 逆置链表
void reverseList() {
ListNode* prev = nullptr;
ListNode* current = head;
ListNode* nextTemp;
while (current != nullptr) {
nextTemp = current->next;
current->next = prev;
prev = current;
current = nextTemp;
}
head = prev;
}
// 遍历并打印原链表
void printOriginal() {
ListNode* temp = head;
while (temp != nullptr) {
std::cout << temp->val << " -> ";
temp = temp->next;
}
std::cout << "NULL\n";
}
// 遍历并打印逆置后的链表
void printReversed() {
ListNode* temp = head;
while (temp != nullptr) {
std::cout << temp->val << " -> ";
temp = temp->next;
}
std::cout << "NULL\n";
}
};
```
使用这个类,你可以创建一个链表,对其进行逆置,然后分别打印出原链表和逆置后的链表。
阅读全文