定义单链表的类,实现一个带头结点的单链表的逆置,并将逆置前后的单链表分别遍历输出。单链表中各结点的值和结点个数等自定。 用C++程序编写
时间: 2024-10-11 09:11:22 浏览: 40
单链表存储叶子节点并逆置
4星 · 用户满意度95%
在C++中,我们可以创建一个`ListNode`结构体表示链表节点,然后定义一个`LinkedList`类来管理整个链表,包括逆置操作。以下是简单的实现:
```cpp
#include <iostream>
// 定义链表节点结构
struct ListNode {
int val; // 节点值
ListNode* next; // 指向下一个节点的指针
ListNode(int x) : val(x), next(nullptr) {} // 构造函数
};
// 链表类
class LinkedList {
private:
ListNode* head; // 头节点
public:
LinkedList() : head(nullptr) {}
// 添加节点到链表尾部
void addNode(int val) {
if (head == nullptr) {
head = new ListNode(val);
} else {
ListNode* curr = head;
while (curr->next != nullptr) {
curr = curr->next;
}
curr->next = new ListNode(val);
}
}
// 逆置链表
void reverseList() {
ListNode* prev = nullptr;
ListNode* curr = head;
ListNode* nextTemp;
while (curr != nullptr) {
nextTemp = curr->next;
curr->next = prev;
prev = curr;
curr = nextTemp;
}
head = prev; // 更新头节点
}
// 遍历并打印原链表
void printOriginal() {
ListNode* temp = head;
while (temp != nullptr) {
std::cout << temp->val << " -> ";
temp = temp->next;
}
std::cout << "nullptr" << std::endl;
}
// 遍历并打印逆置后的链表
void printReversed() {
ListNode* temp = head;
while (temp != nullptr) {
std::cout << temp->val << " -> ";
temp = temp->next;
}
std::cout << "nullptr" << std::endl;
}
};
int main() {
LinkedList list;
list.addNode(1); // 添加节点1
list.addNode(2);
list.addNode(3);
// 打印原始链表
std::cout << "Original linked list: ";
list.printOriginal();
// 逆置链表
list.reverseList();
// 打印逆置后的链表
std::cout << "Reversed linked list: ";
list.printReversed();
return 0;
}
```
在这个例子中,我们首先创建了一个链表,并添加了几个节点。然后调用`reverseList`方法逆置链表,最后分别遍历和打印原链表和逆置后的链表。
阅读全文